Score:0

Crypto

RSA not encrypting properly when e=d?

Paul

9/17/23, 7:26 PM

I'm trying to implement the RSA algorithm with some random (valid as far as I know) generated values but for this combination, encryption/decryption doesn't work.

message = 324
p = 3
q = 29
n = 87
e = 15
d = 15

Which give both and encrypted and decrypted answer of 63

I'm guessing I made and error while generating the values but I don't exactly know where.

I know e and d shouldn't be equal for security reasons, but from my understanding encryption should still work.

0 + 0

rsa

Daniel S

9/17/23, 7:35 PM

It does work in the sense that 324 mod 78 is 63. RSA cannot cope with messages large than the modulus and at best the remainder of the message with respect to the modulus is returned.

kelalaka

9/18/23, 10:50 AM

I've failed to find a dupe ( hope one can find one or someone wants to write an answer). Remember $c = m^e \bmod N$ so RSA is performed under modulus...

Score:4

Crypto

Pedro Campones

9/18/23, 12:56 PM

I believe the problem is linked to the size of the message rather than the choices of $e$ and $d$.

When deciphering a message, we don't get the result of the message m but rather m mod N. With $N$ being 87.

If the size of the message is smaller than N then we know that $m = m \bmod N$, however this does not happen otherwise.

Observing this example in particular we have that $63 = 324 \bmod 87$, and so the deciphering process acted accordingly with the expected.

As for why the encrypted value is also 63 I believe it was sheer misfortune. The keys and N are quite small, so the chance for suspicious combinations is higher than with real parameterizations.

I may be missing some forbidden pattern in the choice of message, given that the calculations only apply to $m < N$, but if the program works for messages lower than 87, then there should be no problem in having $d = e$.

0 + 0

Don Freecs

9/19/23, 11:00 PM

what about an attacker who uses always d=e as a first test attack ? is it indeed a problem ?

user253751

9/20/23, 9:08 AM

@DonFreecs why d=e though? same chance of success as if you try d=1 or d=3 or d=12345 or d="hello I am an insecure key"

Don Freecs

9/20/23, 2:25 PM

@user253751 indeed so it is a problem to use it ^^

Pedro Campones

9/21/23, 3:29 PM

For most values of p and q, it's not possible for d=e. In order for RSA to work it's necessary that *de = 1 mod (p - 1)(q - 1)*. The higher the value of N, the lower the likellyhood of this happening.