Hacker News new | past | comments | ask | show | jobs | submit login
Restrictions for p,q,d,e in RSA for encrypting English Alphabets?
2 points by shivajikobardan 5 months ago | hide | past | favorite | 2 comments
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 % n

PT=(CT)^d % n

CT= Cipher Text

PT=Plain Text

ed/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 )




Any practical implementation avoids encrypting individual characters for this and other reasons. Wikipedia goes into some detail about chosen–plaintext and chosen–ciphertext attacks, and about some of the different forms of message padding that have been invented to secure against those attacks. The result is that RSA is applied not to individual bytes, but to blocks made of dozens of bytes at a time. Some of the bytes in each block come directly from the message to be encrypted, others are null or have other known values, and some will be computed using hash functions.


See generally

https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

To the original poster, see also

https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...

One should never use "textbook RSA" for secure communications. It has problems with plaintext malleability (that is, there's a predictable way that an attacker can change the plaintext, possibly meaningfully, by changing the ciphertext), with some number-theoretic attacks, and more. Also, with textbook RSA, the message size is limited to the size of the modulus (e.g. with a 2048-bit modulus, you could never send more than 2048 bits of plaintext in a single message).

You can also become familiar with many of these problems by working through Thomas Ptaček's Cryptopals exercises.

https://www.cryptopals.com/

In these exercises, you implement famous attacks against naive versions and inappropriate applications of ciphers, including RSA.

Most ciphers provide confidentiality properties under highly idealized conditions where an attacker is given the least prior knowledge and least ability to influence the communications process, and where mathematical quirks that could lead to a mathematical solution of the cipher are assumed not to occur. This means that other kinds of constructions need to be used in order to produce a system that's secure in practice. An analogy is that one might use a hash for message authentication, based on the claim that the hash is secure in certain settings -- but this may be vulnerable to length extension attacks. Or one might use a block cipher in ECB mode, based on the same sort of claim -- but this may be vulnerable to several mode-of-operation attacks such as recognizing repeated encryptions of the same plaintext.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: