Is this public key encryption?

  • Thread starter Thread starter DaveC426913
  • Start date Start date
DaveC426913
Gold Member
Messages
23,872
Reaction score
7,908
TL;DR Summary
I mean, sure, it only uses a key that has 365 combinations...
I've tried to intuit public key encryption but never quite managed.
But this seems to wrap it up in a bow.

1758918719818.webp


This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher.

Is this how PKE works?

No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
 
Technology news on Phys.org
No, that's something like a one-time pad. There's a single secret that can be used for encryption and decryption.

The thing about public key encryption is that I can share the encryption key with you and you still can't decrypt a message. Or (more precisely) you need a very large computer and a lot of time to deduce the decryption key from the encryption key. Here, anybody who knows the birthdate (which is the secret key) can both encrypt and decrypt.

It's clever, though.
 
  • Like
Likes Hornbein, Nugatory and FactChecker
My (non-expert) two cents:
Suppose I broadcast a "public key": aieo19gkeu, and say that anyone can use it to encrypt and send me a message that nobody, except myself, can decrypt. ADDED: aieo19gkeu can not be used to decrypt a message that it encrypted. I am the only one who knows the private key that can decrypt a aieo19gkeu - encrypted message. Even the sender can not decrypt it, (but he already knows what the message is).

This doesn't seem the same as your example.

ADDED: Of course, I wouldn't really "broadcast" the public key. I would just not worry so much if someone intercepted it. All the interceptor could do is send me messages. He could not decrypt and read the legitimate messages.
 
Last edited:
DaveC426913 said:
I've tried to intuit public key encryption but never quite managed.
Try this:

I send you a box and a padlock that's currently open. I have the key to the padlock, but no one else does.

You put your message into the box, put the padlock around the hasp, and lock it. Then you send it back to me.

Putting your message into the box and locking it with the padlock corresponds to encrypting your message with my public key. The difference, of course, is that decrypting the message without knowing my private key is many, many, many, many, many orders of magnitude more difficult than picking a padlock without having its key (or cutting the padlock, for that matter).
 
FactChecker said:
ADDED: Of course, I wouldn't really "broadcast" the public key.
You might want to, as it makes it possible to prove that a message came from you. Say you want to make a public proclamation that is unquestionably from you instead of an imposter…. You would encrypt it using your private key, then release that to the world. As long as your public key is widely known, everyone will be able to read your statement and will know that it could only have come from you.
(In practice digital signing algorithms are more sophisticated than that, but the principle is the same: that which can be read using the public key must have come from the owner of the private key).
 
  • Like
Likes Ibix, FactChecker and PeterDonis
https://medium.com/techanic/the-math-in-public-key-cryptography-in-simple-words-with-examples-e3a18cb4fa85 said:

Creating public and private keys​

Public and private keys are created using mathematical functions based on modular arithmetic and the properties of co-prime numbers. Here is a step-by-step example of how public and private keys are created:
  1. Select two prime numbers: To create a public and private key pair, two different prime numbers must be selected. For example, let’s choose p = 17 and q = 23.
  2. Compute n: Compute the product of the two prime numbers. n = p * q = 17 * 23 = 391.
  3. Compute φ(n): Compute the Euler’s totient/phi function of n, which is the number of positive integers less than n that are co-prime to n. φ(n) = (p-1) * (q-1) = 16 * 22 = 352.
  4. Choose a co-prime number: Choose a number e that is co-prime to φ(n). In other words, e should have no common factors with φ(n) other than 1. For example, let e = 5.
  5. Compute the private key: Compute the private key d, which is the multiplicative/modular inverse of e modulo φ(n). In other words, d is the number such that (d * e) mod φ(n) = 1. In this example, d = 141.
  6. Public and Private Key Pair: The public key is (n, e) and the private key is (n, d).
To encrypt a message m using the public key (n, e), we first convert the message into a number m using a chosen encoding method. Then, we apply the encryption function C(m) = m^e mod n, which generates the encrypted message.

To decrypt the encrypted message C using the private key (n, d), we apply the decryption function D(C) = C^d mod n, which recovers the original message.

For example, let’s say we want to encrypt the message M = “HELLO” using the public key (391, 5). First, we convert the message into a number m = 72736576 using ASCII encoding. Then, we apply the encryption function C(m) = m^e mod n = 72736576⁵ mod 391 = 113.

To decrypt the encrypted message C = 113 using the private key (391, 141), we apply the decryption function D(C) = C^d mod n = 113¹⁴¹ mod 391 = 72736576, which recovers the original message “HELLO”.
 
Nugatory said:
You might want to, as it makes it possible to prove that a message came from you.
Say you want to make a public proclamation that is unquestionably from you instead of an imposter…. You would encrypt it using your private key, then release that to the world. As long as your public key is widely known, everyone will be able to read your statement and will know that it could only have come from you.

(In practice digital signing algorithms are more sophisticated than that, but the principle is the same: that which can be read using the public key must have come from the owner of the private key).
Ohhhhhhh.

That answers one question I never quite understood.

They do publish them. Like, in a catalogue. The intent is for them to be widely known, right?

And now I see why.
 
jack action said:
Creating public and private keys...
See, that's the thing. I see very detailed descriptions of exactly how it works, but that doesn't help me intuit it. With all the math, I can't see the forest for the trees.
 
DaveC426913 said:
See, that's the thing. I see very detailed descriptions of exactly how it works, but that doesn't help me intuit it. With all the math, I can't see the forest for the trees.
What the math says:

There are 2 keys, one than encrypts the message (the public one that anyone can get), and a second one that decrypts the message (the private one that only you can use).

So the message can only be addressed to you and can only be read by you. If you want to respond, the other person will have their own public key (for you to encrypt your message to them) and private key (for them to decrypt it).
 
  • #10
DaveC426913 said:
They do publish them. Like, in a catalogue. The intent is for them to be widely known, right?
That certainly is one application. It uses the public/private keys to allow a person in the public who receives a message that you send to know the authorship because he can decrypt it. It does not protect your message from being read by others.
Another application is what I tried to describe in post #3. It allows people in the public to send you messages that nobody other than you can read, even if they intercept it. It does not confirm authorship of the messages that you receive (since many in the public might have the public key).
It would be possible, using multiple paired public/private keys, to get both benefits.

You mentioned the short length of the key in your example. There is a trade-off regarding the security of a long public key versus the computational efficiency of decrypting a message with a shorter public key. In order to reduce the possibility of a snooper intercepting or figuring out the public key, it can be made huge. That also makes it hard for him to figure out a matching private key. Using a huge public key is computationally expensive, so it is usually only used to decrypt a single-use efficient (symmetric) key at the beginning of a message which can then be used to efficiently decrypt the rest of the massage.
 
  • #11
FactChecker said:
It would be possible, using multiple paired public/private keys, to get both benefits.
And that's how HTTPS and other similar secure protocols like SSH, SFTP, work AFAIK. I create a key pair and send the encryption key to the server, and the server creates a key pair and sends me the encryption key. Then we can both create messages that only the other can decrypt, which we use to send encrypted versions of an otherwise bog standard HTTP conversation.
 
Last edited:
  • Like
Likes FactChecker and jack action
  • #12
jack action said:
What the math says:

There are 2 keys, one than encrypts the message (the public one that anyone can get), and a second one that decrypts the message (the private one that only you can use).

So the message can only be addressed to you and can only be read by you. If you want to respond, the other person will have their own public key (for you to encrypt your message to them) and private key (for them to decrypt it).
A little too abstract. :)

The reason I started this post with the example I did is because I thought (erroneously) it was a perfect balance of accurate, yet digestible, detail: numbers I understand - a mere few digits, but enough to get the idea that they're in principle, private.

And that it was the principle put into practice in a way I could see the (sufficiently small) moving parts. I could see with my eyes how the number he invented would logically lead the receiver from their own private number to the decrypted message.

That's why I thought this example was worth posting.

Alas, it is not analogous. :(
 
  • #13
DaveC426913 said:
That's why I thought this example was worth posting.

Alas, it is not analogous. :(
The main difference is that your example uses a symmetric key, "your birthday MM/DD/YYY", known by both parties, to both encrypt and decrypt the message ("my phone number").
A public/private key system uses asymmetric keys, one to encrypt and another to decrypt. The person who owns the public/private key-pair knows both keys. The public person only knows the public key and (in theory) can not determine the private key. This prevents the public person from performing one of the encrypt/decrypt functions, depending on how the asymmetric keys are being used.
 
  • Like
Likes DaveC426913
  • #14
I have to repeat the point I made in #2, though, that this is a neat application of symmetric key encryption. It protects the author's information and gives a the wallet's owner enough to get in touch while acting as an initial authentication. It's elegant.
 
  • #15
Ibix said:
I have to repeat the point I made in #2, though, that this is a neat application of symmetric key encryption. It protects the author's information and gives a the wallet's owner enough to get in touch while acting as an initial authentication. It's elegant.
Yes, in this case. This case has a very short message where it is hard to know when a decrypted result is a valid phone number. (But decrypting to a valid local area code might give a clue.) Given a longer text message, it might not take long to decrypt it by brute force.
 
  • #16
FactChecker said:
Yes, in this case. This case has a very short message where it is hard to know when a decrypted result is a valid phone number. (But decrypting to a valid local area code might give a clue.) Given a longer text message, it might not take long to decrypt it by brute force.
True. Which is why the finder will certainly employ two-factor identification: While one or two enterprising crypto-enthusiasts might make the effort to deduce the number and call it, the finder can still ask any number of skill-testing questions about the contents of the wallet.
 
  • #17
FactChecker said:
This case has a very short message where it is hard to know when a decrypted result is a valid phone number. (But decrypting to a valid local area code might give a clue.)
At nine digits, it's actually a pretty short number if it includes an area code (which it probably does since it starts with a zero) and pretty long if it doesn't. UK phone numbers are eleven digits, of which five is area code.
 
  • #18
DaveC426913 said:
A little too abstract. :)

The reason I started this post with the example I did is because I thought (erroneously) it was a perfect balance of accurate, yet digestible, detail: numbers I understand - a mere few digits, but enough to get the idea that they're in principle, private.

And that it was the principle put into practice in a way I could see the (sufficiently small) moving parts. I could see with my eyes how the number he invented would logically lead the receiver from their own private number to the decrypted message.

That's why I thought this example was worth posting.

Alas, it is not analogous. :(
This is what he would have written to use public and private keys (using keys in post #6):

Solve these two equations with your date of birth (DDMMYYYY) and phone number (AAABBBCCCC) and write the answers below:

DDMMYYYY^5 mod 391 =
AAABBBCCCC^5 mod 391 =

Then, if someone left two numbers on the ad, say DOB and PHONE, the person who placed the ad would read the answers, decode these numbers with their private keys, and get:

DOB^141 mod 391 = DDMMYYYY
PHONE^141 mod 391 = AAABBBCCCC

Knowing the date of birth matches, they can call the decoded phone number.

The advantage is that the ad can be in a public place, and nobody - except the one with the private key - can deduce the date of birth from the number DOB or the phone number from the number PHONE ... AND you don't have to leave your phone number in a public place as well.
 

Similar threads

Back
Top