Quick question about asymmetrical encryption

[monoman]

In trying to understand asymmetrical encryption, I thought of a way to do it that doesn't involve large prime numbers. If someone can explain to me why it isn't done in the way I thought of, I'll have a firmer grasp of the way it's actually implemented.

So, Person A wants to send a secret email to person B:

(1) Person A adds a different random number to each letter of the message and, keeping a note of those random numbers, sends the email to person B.

(2) Person B adds a different random number to each letter of the message and, keeping a note of those random numbers, sends the email back to person A.

(3) Person A takes off the numbers they added and sends it back to person B

(4) Person B takes off the numbers they added and they have the unencrypted message.

 

[drkitten]

In trying to understand asymmetrical encryption, I thought of a way to do it that doesn't involve large prime numbers. If someone can explain to me why it isn't done in the way I thought of, I'll have a firmer grasp of the way it's actually implemented.

So, Person A wants to send a secret email to person B:

(1) Person A adds a different random number to each letter of the message and, keeping a note of those random numbers, sends the email to person B.

(2) Person B adds a different random number to each letter of the message and, keeping a note of those random numbers, sends the email back to person A.

(3) Person A takes off the numbers they added and sends it back to person B

(4) Person B takes off the numbers they added and they have the unencrypted message.

It's not secure because Eve, the traditional eavesdropper, can intercept the messages and recover the original plaintext.

Specifically, A transmits M+X. B retransmits M+X+Y. A subtracts X and retransmits M+Y.

At this point, Eve compares the second and third transmissions and determines the value of X. She then subtracts X from the first transmission and gets M.

You've come very close to re-inventing Shamir's three-pass protocol, though.

 

[sphenisc]

To summarise

1) X+A -->
2) <-- X+A+B
3) X+B -->
4) X

If some intercepts messages 1 and 2 they can calculate the B numbers.
If they intercept 3 they can then work out X.

ETA: Beaten to it. Grrr

 

[drkitten]

In trying to understand asymmetrical encryption, I thought of a way to do it that doesn't involve large prime numbers. If someone can explain to me why it isn't done in the way I thought of, I'll have a firmer grasp of the way it's actually implemented.

Further to above. Basically, you've rediscovered the need for a "one-way function." The problem with your approach is that it's as easy for Eve to subtract Y as it is for B(ob) to add Y.

If you use a one-way problem, like factoring or discrete logs, then it becomes much easier for Bob to multiply than for Eve to factor, which means that Bob can hide his message more easily than Eve can discover it.

 

[monoman]

Doh! Quick question, quick answers.

Thanks to both of you, the need for a 'one-way function' is now plain to see.

 

[rjh01]

Another problem with codes is not just Eve. It is the danger that the enemy might capture one of the sending stations with all its equipment. Once you know how to encode the message you can reverse the process.

Another problem is how to get the codes to everyone you want and know that it has not be read by the enemy in the meantime?

 

[Salerio]

What you've described is a reasonable encryption system, except we wouldn't just use a simple function such as "add". In fact what you've described is used.

If we do it this way

A creates a message m and encrypts it with a function f

f(m) -> B

f(m) is transfered to B who encrypts the entire message with his own key and sends it back to A

g(f(m)) -> A

A removes his key and sends it to B by applying f' to the entire message

f'(g(f(m))) -> B

B can then decrypt the message by applying g'

g'(f'(g(f(m))))

if the functions are chosen correctly then this can be very secure. This does need functions such that f'(g(f(m))) = g(m) for a symmetric key system the keys used in both f'(m) and f(m) will be the same. If the message is intercepted during transit then only encrypted text will be found.

It's not particularly efficient, you need three message passes and four encryption/decryption operations just to send a message. One good thing is that no keys need to be exchanged. With PKI using asymmetric keys you can publish foreign keys so anyone can send a secure message to you.

The processing needed for asymmetric cyphers is very much higher than symmetric cyphers and is generally only used to encrypt the symmetric keys while the symmetric cypher is used to encrypt the main message.

 

[Mister Earl]

I wrote my own method when I was a kid in a copy of visual basic. Basically, there was the text string, the user supplied encryption key (alphanumeric, symbols work too), and a software key that stayed within the program. It'd encrypt in this manner: It'd strip the leftmost character out of each of the three strings, render their ASCII code numbers, add them, then render back into a character. If it was over 255 it'd subtract it. Then it'd store this character into the finished string value, then go on to strip off the next characters of the three strings. If either password wasn't long enough, it would simply repeat. It was decoded by doing pretty much the same thing in reverse. I couldn't tell you how strong it was, but it worked out pretty well. A couple of other kids my age tried to "crack" it, but they just assumed it was a simple letter substitution and never succeeded.

 

[JoelKatz]

Another problem with codes is not just Eve. It is the danger that the enemy might capture one of the sending stations with all its equipment. Once you know how to encode the message you can reverse the process.

Okay, you've captured a sending station. The encrypting process is as follows:

1) Encode the message as a hexadecimal number containing more than 300 bits and fewer than 750 bits. Add random padding if needed or break the message into multiple chunks if needed.

2) Raise that hexadecimal number to the 65,536 power.

3) Take the result from step 2 modulo this hexadecimal number:
00:b5:15:e6:9c:d1:09:06:4a:ec:d5:43:66:d9:60:
df:15:ff:55:a1:f9:ad:73:5f:0a:96:22:76:7d:38:
0f:94:3f:3f:17:65:d3:db:73:14:8b:4b:c4:32:32:
2b:a8:bb:6c:cf:3e:ec:5b:62:28:c4:5a:49:3f:39:
35:8f:08:f0:01

4) The result of the modulus operation is the encrypted message, expressed in hexadecimal bytes as the constant above have been specified.

Please show me how you reverse it.

These types of encryption schemes are based on "trapdoor" operations. These are operations that, for practical purposes, cannot be reversed knowing only how to run them in the forward direction. However, the constants are carefully chosen to conceal a "trapdoor" that the person who created the cipher knows and that allows them, and only them, to take another practical path that has the effect of reversing the original operation.

In this case, the number I chose for step 3 is the product of two primes that only I know. Thus only I can calculate the exponent needed to reverse the exponentiation operation given only the result after the modulus operation.

Note that you can always break these schemes in theory. If nothing else, you can try every possible message, follow this process, and see which plaintext generates a captured message. For this particular scheme, it's more practical to try to factor the modulus. For the small number I chose, this could be done with a decent sized network of distributed computers. Real-world applications use numbers four times this length, and would take centuries to break even with every computer currently in existence.

 

[rjh01]

Okay, you've captured a sending station. The encrypting process is as follows:

1) Encode the message as a hexadecimal number containing more than 768 bits and fewer than 1,000 bits. Add random padding if needed or break the message into multiple chunks if needed.

2) Raise that hexadecimal number to the 65,536 power.

3) Take the result from step 2 modulo this hexadecimal number:
25:57:02:e1:9e:74:85:51:63:36:ea:eb:9c:49:d9:
50:a8:57:c4:06:2c:8a:cd:65:4d:e2:d1:a9:25:01:
c9:68

4) The result of the modulus operation is the encrypted message, expressed in hexadecimal bytes as the constant above have been specified.

Please show me how you reverse it.

These types of encryption schemes are based on "trapdoor" operations. These are operations that, for practical purposes, cannot be reversed knowing only how to run them in the forward direction. However, the constants are carefully chosen to conceal a "trapdoor" that the person who created the cipher knows and that allows them, and only them, to take another practical path that has the effect of reversing the original operation.

Yes, I agree, there are some codes that cannot be reversed (short of a quantum computer). However others (such as the Germans used in WW2) that can be broken in this way. The British in WW2 went out of their way to capture the codes. Even gave orders that a convoy could be sacrificed to get the codes.

 

[JoelKatz]

Yes, I agree, there are some codes that cannot be reversed (short of a quantum computer). However others (such as the Germans used in WW2) that can be broken in this way. The British in WW2 went out of their way to capture the codes. Even gave orders that a convoy could be sacrificed to get the codes.

This thread is about asymmetrical encryption though.

 

[drkitten]

Another problem with codes is not just Eve. It is the danger that the enemy might capture one of the sending stations with all its equipment. Once you know how to encode the message you can reverse the process.

Not since 1880 or thereabouts has that been a problem.

Modern militaries assume that you have copies of all the equipment. What you don't have is the 'key,' which may not even be written down (which makes it difficult to capture). Having a copy of the Enigma machine is pretty much useless; there are so many ways that the wires and wheels can be put together that you can't break a message by brute analysis. (And, indeed, Turing and company couldn't break messages without either cribs or stolen key lists, despite having had copies of the Enigma machine since before the War.)

The advantage of asymmetric encryption is that the key used to encrypt is different from the key used to decrypt, so even if you can capture the encryption key, you can't use it to decrypt a message (and indeed the spy sending messages back to HQ probably doesn't even know the decryption key).

 

[geni]

Not since 1880 or thereabouts has that been a problem.

Modern militaries assume that you have copies of all the equipment. What you don't have is the 'key,' which may not even be written down (which makes it difficult to capture). Having a copy of the Enigma machine is pretty much useless;

Yes and no. It meant that unlike the Lorenz machine the allies didn't have to work out how it worked which in the case of the Lorenz machine required a significant error on the german part and still took months.

there are so many ways that the wires and wheels can be put together that you can't break a message by brute analysis.

Well you pretty much can today (actualy there are weaknesses in the encrtion scheme so you don't have to go for pure brute force).

(And, indeed, Turing and company couldn't break messages without either cribs or stolen key lists, despite having had copies of the Enigma machine since before the War.)

The prewar Enigma machine was somewhat weaker than the latter war version though.

The advantage of asymmetric encryption is that the key used to encrypt is different from the key used to decrypt, so even if you can capture the encryption key, you can't use it to decrypt a message (and indeed the spy sending messages back to HQ probably doesn't even know the decryption key).

You can attack pure RSA by using the key to encrypt likely planetexts and seeing if they output matches but that just the reason no one uses pure RSA.

 

[JoelKatz]

You can attack pure RSA by using the key to encrypt likely planetexts and seeing if they output matches but that just the reason no one uses pure RSA.

Exactly. RSA itself is a cryptographic primitive that can be used to build secure cryptographic systems. If you eat the recipe, however, you may get indigestion.

Specifically, the input to the RSA algorithm must not be predictable by an attacker. The current state of the art solution to this problem is OAEP.
http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding

 

[not daSkeptic]

The advantage of asymmetric encryption is that the key used to encrypt is different from the key used to decrypt, so even if you can capture the encryption key, you can't use it to decrypt a message (and indeed the spy sending messages back to HQ probably doesn't even know the decryption key).

Another advantage is the lack of any need for the parties to exchange sensitive key material.