rsaencryption-asymmetric

The public key encrypted value can get decrypted with someone else’s private key

Today I was just testing my code and found that:

Say Bob and Alice have keypairs (pub1,priv1) and (pub2,priv2) respectively.

If Bob encrypts messages with pub2 (Alice’s public key) and then he again encrypts that cypher-text with priv1 (bob’s private key), it returned same bytes as messages! I.e. bob was able to decrypt cypher text encrypted with pub2

But it turns out that when message was encrypted by pub2 and priv1, they strangely generated same cypher text, also priv1 and priv2 both can decrypt them regardless…

Here's the calculations I performed:

e = 65537

//Bob's stuff
p = 512 bit prime number
q = 512 bit prime number
n = p * q (where * means multiply)
on = (p-1) * (q-1)
d = modulo inverse of (e, on)

//Alice's stuff
p1 = 512 bit prime number
q1 = 512 bit prime number
n1 = p1 * q1
on1 = (p1-1) * (q1-1)
d1 = modulo inverse of (e, on1)

so when say I want to encrypt a = 97 (according to utf8) (let's forget about vulnerabilities of using small number for encryption)

so I tried encrypting like: c1 = mod(97 * e, n1) i.e. encrypted with Alice's public key.

Now I want Alice to verify that the message belongs to Bob only (let's not talk about x509 as of now)

so I encrypted that cyphertext c1 with Bob's private key priv1 (or d) like:

c2 = mod(c1 * d, on)

So that Alice can decrypt it twice and make sure that it belongs to Bob only as:

c3 = mod(c2 * e, n) //as we encrypted c1 with bob's pvt key, now it should be decrypted using his public key.

and to decrypt the message:

c4 = mod(c3 * d1, on1) //should give original message i.e. 97

BUT, it however does not happen the way it should, rather mod(97 * e, n), mod(97 * e, n1), mod(97 * e, on), mod(97 * e, on1) gives same output.. How's that possible? (n, on) and (n1, on1) are quite different. Also I was able to decrypt message encrypted with above method with anyone's private key whose corresponding public key was NOT used for encryption at all.

Solution

  • The RSA cryptosystem uses modular exponentiation as a primitive operation rather than modular multiplication as you appear to be employing. If n = p * q is the RSA modulus, the product of primes p and q, and e and d are the encrypt and decrypt exponents respectively, then encryption is c = xe mod n and decryption is x = cd mod n, where x is the plaintext integer. Of course modular multiplication is a key component of modular exponentiation. In python you can use the three-argument form of the built-in pow function to easily and efficiently perform modular exponentiation, so simply

    c = pow(x, e, n)
x = pow(c, d, n)

    Using sage to explore RSA (includes RSA tutorial) is also relatively easy. In sage you can indicate that the arithmetic is to be done in the ring of integers modulo n by something like

    R = Integers(n)
x = R(97)
c = x ^ e
decrypted = c ^ d
print(decrypted == x)  # prints True

    Notice that in sage ^ is the exponentiation operator, whereas in python it is the exclusive or (xor) operator.

    If the ring of integers modulo n is a little too exotic for you then you can just use regular integer arithmetic in sage with the mod() and power_mod() functions.