# Is it possible to use the root function to attack RSA?

Sorry for my silly question, but I have some doubts on this point. I'm trying to explain it better with an example.

Suppose you use RSA to sign a package and you have the public key. If the signature is generated by the server with its secret key you are able to decipher it because you have the public key and verify the integrity of your package. Suppose I make a "fake" package and I'm able to create a correct signature like this:

00 01 FF .. .. FF 00 ASN.1 SHA1


due to the deciphering process:

cleartext = C^e mod n


I can encrypt my signature in this way:

C mod n = root(cleartext,e)


and make a correctly padded signature without knowing the private key?

Example:

e = public exponent = 3

C mod n = cubicroot (cleartext)

• But e is not already known? Isn't e the public exponent? – FabioLovi Apr 6 '17 at 12:39
• How do you propose to calculate that root function? – CodesInChaos Apr 6 '17 at 14:55

If root is just the function from calculus, then

at most ceil(root(n,3)) elements cleartext of ​ {0,1,2,3,...,n-2,n-1}
are such that root(cleartext,3) is an integer
and
when its output is not an integer, that output is not a valid signature,
since valid signatures must be elements of ​ {0,1,2,3,...,n-2,n-1}

.

If root is modular, then for carefully chosen large moduli n, there's no publicly known
feasible classical way to have a non-negligible probability of computing root.
However, quantum computers change things quite significantly.

Finding the cubic root modulo n seems to be non-trivial. You may read about it in StackExchange’s Mathematics site.

Nowadays, the 65537 is generally chosen for the public exponent, rather than 3, which probably makes the discrete root more complicated to calculate.

You can do this. But only if you can solve the discrete logarithm problem! Your "root" function actually has to find the group element c such that c^e = k where c and k are group elements of the group Z mod n and e is a natural number.

If you can find an efficient implementation of such a function, you will become very famous.

• e is known, the OP wants to compute C. – CodesInChaos Apr 6 '17 at 13:42
• As CodesInChaos said, this is not the discrete logarithm problem. The discrete logarithm problem would be to find e knowing c and k while, here, you have to find c knowing e and k. – user2233709 Apr 6 '17 at 17:26