RSA to encrypt English Alphabets, any restrictions?

[shivajikobardan]

Homework Statement

Is there some restrictions on values of p,q,d,e etc in RSA algorithm while trying to encrypt English Ciphertext?

Relevant Equations

RSA algorithm, modulus solving, Euler's formula for GCD calcualation

Is there some restrictions on values of p,q,d,e etc in RSA algorithm while trying to encrypt English Ciphertext?
I'll present few cases of RSA encryption:

$CT=(PT)^e mod \, n$

$PT=(CT)^d mod \, n$

CT= Cipher Text

PT=Plain Text

e*d/m should give remainder 1, where;

m=(p-1)*(q-1); where p, q are 2 prime numbers.

A) Sender takes p=3, q=11.

The value of e=3, d=7 satisfied the remainder=1 condition.

So, if sender wants to send "SELL":

S=19, CT=28

E=5. CT=26

L=12, CT=12

L=12, CT=12(? What to do to not get the cipher text same as plain text without making things too complex and still being able to do it in paper manually?)

B) p=2, q=11

e=3,d=7

I'll only write CT here(i.e S=17 means that 17 is a cipher text for S after RSA encryption):

S=17

E=15

L=12

L=12 (Same here? why? Because of d,e being the same?)C) p=13, q=11

d=13, e=37

So,

S=95

E=93

L=12

L=12 (Again got the same value, what is this? Even with different values of p,q,d,e!)

Questions:

a) Is there any restrictions if among p or q, anyone should be greater?

b) Is there any restrictions like which of the d or e should be greater?

I know e<m and e>1

And e should be relatively prime to m, i.e GCD(e,m)=1.

GCD(13,120)=1

For d,

de mod m=1

c) Would there be any cases, where while decryption, we would not be able to get the plain text due to some reasons (like if not choosing values properly for d,e,p,q in english alphabet encryption? This is the main confusion that is making me ask this )

 

[Office_Shredder]

This is not correct. You can't encrypt the individual letters, or else you are vulnerable to the same attacks any mono alphabetic Cypher allows.

Instead you have to turn the whole message into a single number. For example you can say that you have a base 27 representation of a number, for which sell would be $(19)(5)(12)(12)=19*27^3+5*26^2+12*26+12=377681$ and you would do your work with that number. When the other side decrypts it, they know to turn it back into base 27 to get the letters.

In practice what I described is vulnerable to attack anytime you send a short message, so like all things in cryptography the real story is more complicated. For example
https://en.m.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding

 

[shivajikobardan]

This is not correct. You can't encrypt the individual letters, or else you are vulnerable to the same attacks any mono alphabetic Cypher allows.

Instead you have to turn the whole message into a single number. For example you can say that you have a base 27 representation of a number, for which sell would be $(19)(5)(12)(12)=19*27^3+5*26^2+12*26+12=377681$ and you would do your work with that number. When the other side decrypts it, they know to turn it back into base 27 to get the letters.

In practice what I described is vulnerable to attack anytime you send a short message, so like all things in cryptography the real story is more complicated. For example
https://en.m.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding

There's no way anyone can do $377681^113$ calculation by pen and paper! It'd be huge! I feel like you're correct though! But I've not seen any textbooks explaining like you said (Neither they're explaining like I said). They're not explaining encrypting english alphabet at all.(The books I've in my bag).

 

[Office_Shredder]

If your goal is really to do it by hand, then I agree you have to do it letter by letter.

That said, you have the wrong concern with my example. You're computing everything mod n, which you can do in between computing consecutive powers, so the arithmetic is actually not that hard. The real issue if you choose to stick with your p and q is that you can only encode 33 distinct messages, so there is no way to know what I actually sent. You would have to pick new primes.

If you want to stick with your setup, there's no good way to guarantee a letter doesn't go back to itself, but that's OK if it does. It shouldn't be easier for an attacker to figure out that L is still L than it would be to figure out any other letter mapping.

 

[shivajikobardan]

If your goal is really to do it by hand, then I agree you have to do it letter by letter.

That said, you have the wrong concern with my example. You're computing everything mod n, which you can do in between computing consecutive powers, so the arithmetic is actually not that hard. The real issue if you choose to stick with your p and q is that you can only encode 33 distinct messages, so there is no way to know what I actually sent. You would have to pick new primes.

If you want to stick with your setup, there's no good way to guarantee a letter doesn't go back to itself, but that's OK if it does. It shouldn't be easier for an attacker to figure out that L is still L than it would be to figure out any other letter mapping.

Which p,q values sir you talking about? The only thing I've heard is that p*q should be more than the number of alphabets you're encoding. i.e more than 26.

 

[Office_Shredder]

Which p,q values sir you talking about? The only thing I've heard is that p*q should be more than the number of alphabets you're encoding. i.e more than 26.

Right. This is really bad advice if you are trying to do actual cryptography. You need pq to be bigger than the number of messages you want to send, and ideally much bigger so you can pad extra stuff in and make it harder to decrypt.

If you just want to try doing it by hand and encode one letter at a time, then what you're doing is fine, but if you want to understand the cryptography, not just the math, you should understand why this is not a satisfying encoding. This is ignoring how easy it is for someone to factor your public key which is obviously also an issue.

 

[shivajikobardan]

Right. This is really bad advice if you are trying to do actual cryptography. You need pq to be bigger than the number of messages you want to send, and ideally much bigger so you can pad extra stuff in and make it harder to decrypt.

If you just want to try doing it by hand and encode one letter at a time, then what you're doing is fine, but if you want to understand the cryptography, not just the math, you should understand why this is not a satisfying encoding. This is ignoring how easy it is for someone to factor your public key which is obviously also an issue.

Yes, my goal i think is to understand RSA rather than become a cryptographer as this course is Undergraduate course and isn't even cryptography subject. This is other subject where 1 part is cryptography.

 

[Vanadium 50]

If you want to stick with your setup, there's no good way to guarantee a letter doesn't go back to itself, but that's OK if it does.

Better than OK. In WW2 there was an Enigma intercept that cryptographer Mavis Lever noticed hadn't a single L in it. Since the Enigma never encrypts a letter to itself, she deduced the message was nothing but L's. This was a big step in determining the day's keys.

I am sure that the sender of the message really caught L for that.