RSA to encrypt English Alphabets, any restrictions?

• Comp Sci
• shivajikobardan
In summary, the RSA algorithm has restrictions on the values of p, q, d, and e when encrypting English ciphertext. The values of e and d must satisfy the condition of e*d/m giving a remainder of 1, where m=(p-1)*(q-1) and p and q are prime numbers. There are also restrictions on the choice of d and e, such as e<m, e>1, and e being relatively prime to m. It is important to note that the RSA encryption does not work by encrypting individual letters, but rather by turning the entire message into a single number. This can be done using a base 27 representation, where each letter is assigned a number and the entire message is converted
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 greate
r?

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 )

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

Office_Shredder said:
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
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).

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.

Office_Shredder said:
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.

shivajikobardan said:
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.

Office_Shredder said:
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.

Office_Shredder said:
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.

1. What is RSA encryption and how does it work?

RSA (Rivest-Shamir-Adleman) is a type of public-key encryption algorithm used to secure data transmission over the internet. It works by generating a public and private key pair, where the public key is used to encrypt data and the private key is used to decrypt it.

2. Can RSA encrypt any type of data, including English alphabets?

Yes, RSA can encrypt any type of data, including English alphabets. It can also encrypt numbers, symbols, and other languages.

3. Are there any restrictions on the length of the message that can be encrypted using RSA?

Yes, there are restrictions on the length of the message that can be encrypted using RSA. The maximum length of the message depends on the key size used for encryption. For example, with a 1024-bit key, the maximum message length is 117 bytes.

4. Can RSA be cracked or hacked?

RSA is considered a secure encryption algorithm, but like any other encryption method, it is not completely immune to hacking. With enough computing power and time, it is possible to crack RSA encryption. However, the longer the key used, the more difficult it becomes to crack.

5. Is RSA encryption used for all types of data transmission?

No, RSA encryption is not used for all types of data transmission. It is commonly used for securing sensitive data such as financial transactions, online communication, and digital signatures. Other encryption methods may be more suitable for different types of data transmission.

• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• General Math
Replies
1
Views
977
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Programming and Computer Science
Replies
1
Views
689
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
753
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
31
Views
9K
• Engineering and Comp Sci Homework Help
Replies
2
Views
5K
• General Math
Replies
8
Views
3K