Re: Doubts about e and n

From: Spamless (Spamless_at_Nil.nil)
Date: 07/08/05 

Date: Fri, 08 Jul 2005 00:45:08 GMT

On 2005-07-07, Mack <macckone@a_nospamjunk123_ol.com> wrote:
> On 7 Jul 2005 16:16:09 GMT, Unruh <unruh-spam@physics.ubc.ca> wrote:
>
>>"Giox" <giovanniparodi79@yahoo.it> writes:
>>
>>>Hello everybody, I would like to know the standard size for the e
>>>parameter (a^e mod n) when RSA is based on 1024 and 2048 bit lenght.
>>>The target application is cryptocard
>>
>>A prime which is small (to make encryption easy) and which is relatively
>>prime to phi(n). Often one whose binary representation includes only two 1
>>bits. (eg 15, 31), but it is up to you. It is part of the public key.
>
> errr 15 has four 1 bits and 31 has five one bits.
> The common numbers are 3, 17, 257, and 65537
> but for higher security e should be larger.

e=2 (there are four roots so one can send the Jacobi symbol and
parity of the original message to pick the right root - for
n=pq where p and q are primes).

Decoding is provably just as difficult as factoring n.

I don't believe that has been proven even for n=3.
It *may* be possible to find cube roots mod n much more
simply than square roots, but do people really believe that?

So, e can be small. But consider the case e=3 used by three
people and you send the same message with the same padding
(original message M) and send M^3 mod n1, M^3 mod n2 and
M^3 mod n3.

Well, you know M^3 mod each of n1, n2 and n3.

By the Chinese Remainder Theorem, you know M^3 mod n1*n2*n3

Lots of possible values for M^3, but take the principal
residue mod n1*n2*n3. M is smaller than n1, n2 and n3 so
M^3 is smaller than n1*n2*n3. Ooops ... you don't just
have M^3 mod n1*n2*n3 you have M^3! (without taking the result
modulo n1*n2*n3 ... you have it modulo that but know that it
is smaller than n1*n2*n3).

Well, if you know M^3 itself, just take its cube root (that is
easy, while taking the cube root MODULO something is not easy).

If more than one person uses the same modulus, say one correspondent
uses e (exponent) and modulus n and one uses f,n where e and f
are relatively prime ... oops ...

there exist integers (extended Euclidean algorithm) r,s with
re+sf = 1. You have M^e and M^f mod n.

Calculate (M^e)^r*(M^f)^s=M^(re+sf) mod n, but that is M^1=M mod n.
You just decoded it (got M mod n).

So, don't update your "e" to a larger value for the same modulus
and then send someone and old (unpadded) message you sent with
the old value of "e" (if the new, e, called f, is relatively prime
to e, anyone catching both encoded messages can decode to the single
original).

Small values of e are safe in terms of RSA encryption for finding
general roots but, of course, some messages are weak (if the
encoded message happens to be "4" you know the original was "2")
and if you use the same e with multiple moduli, you may wind up
(via the Chinese Remainder Theorem) giving away M^e modulo the
product of the moduli and if M is smaller than the e'th root
of that new modulus (the product of the moduli) (e.g. there
are more than e moduli), it is weak (you have M^e, not just
modulo something). So messages should be properly padded.

Relevant Pages

  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... investigate whether square roots of -1 are in any way relevant. ... I don't see a pattern. ...
    (sci.math)
  • Re: number theory with congruence.
    ... will lift to a solution modulo 3^2. ... Hence, you need to check each of the values 1, 4, and 7 modulo ... If they are roots, then all three values lying above it are roots ... and i finded the interesting algorithm. ...
    (sci.math)
Quantcast