Prev: Method and Logic
Next: Frustration with mathematics
From: Rainer Urian on 30 Jan 2010 12:48
here you are!

we start by
e*d == 1 mod phi(n)

this means
e*d = 1 + k*phi(n)

first one must determine k:
since one can assume p and q are much smaller than n, one can calculate
k = ceil((e*d-1) /n) //ceil = next greatest integer

Then one can calculate phi by
phi = (e*d-1)/k

Now subsitute q = n/p in
phi = (p-1)*(q-1) = p*q -p-q+1 = n - p - q +1
you get
phi = n - p - n/p +1

multiply by p
p*phi = n*p - p^2 - n + p

this gives the quadratic equation:
p^2 + (phi - n - 1)*p +n = 0

you can solve this equation by any real square root approximation (e.g.
Newton) and round to the nearest integer.

BTW, this algorithm will not work in case ed = 1 is only defined mod
lcm(p-1,q-1)


Best Regards,
Rainer























"Mok-Kong Shen" <mok-kong.shen(a)t-online.de> schrieb im Newsbeitrag
news:hk1p2a$t1t$03$1(a)news.t-online.com...
> Rainer Urian wrote:
>
>> Calculating p,q from n,e,d is simple if de = 1 mod phi(n). It is merely
>> solving a quadratic equation in Z.
>
> Could you please tell how to do that by solving one (single) quadratic
> equation in Z?
>
> Thanks,
>
> M. K. Shen
>

From: unruh on 30 Jan 2010 12:56
On 2010-01-30, Rainer Urian <rainer(a)urian.eu> wrote:
> Hello,
> I am wondering if there are two different definitions of RSA keys.
>
> One definition states that one should calculate the secret exponent d as
> (1) e*d = 1 mod phi(n) (= (p-1)*(q-1))
>
> The other states that
> (2) e*d = 1 mod lcm(p-1,q-1)
>
> Both definitions lead to different d values

No, they may lead to different values of d, but the first is a subset of
the second. Note that there are an infinite number of d solving both
equations, and all that solve the first also solve the second.

> I know that this is doesn't matter for RSA based cryptographic operations.
> But it makes a difference if one will calculate CRT parameters from n,e
> and d

Cathode Ray Tube?

> If d is defined accoring to (1) one can use a direct calculation for
> determining p and q
> On the other hand, if d is defined according to (2) one must use a more
> complicated probabilistic algorithm.

Not much more complicated. And many save not only d, but p and q as well
as part of the secret key.

>
> Definition (2) is used by German SECCOS smartcard operating system.
> Can anyone tell me if definition (2) also used in other places?

Both definitions lead to d which can be used to decrypt.
What else do you want? And why do you care?
>
> Thanks,
> Rainer
>
>
>
>
>
>
>
>
From: Rainer Urian on 30 Jan 2010 13:01
> Cathode Ray Tube?

No, Cognitive Retention Therapy
From: unruh on 30 Jan 2010 13:56
On 2010-01-30, Rainer Urian <rainer(a)urian.eu> wrote:
> here you are!
>
> we start by
> e*d == 1 mod phi(n)
>
> this means
> e*d = 1 + k*phi(n)
>
> first one must determine k:
> since one can assume p and q are much smaller than n, one can calculate
> k = ceil((e*d-1) /n) //ceil = next greatest integer

Nope. This may work is e is very very small ( eg 3) but not for
moderately large ea and certainly not if you choose d>n
If e is very small, and d is the smallest solution of ed-1=0 mod(p-1)(q-1).


>
> Then one can calculate phi by
> phi = (e*d-1)/k

Nope.

>
> Now subsitute q = n/p in
> phi = (p-1)*(q-1) = p*q -p-q+1 = n - p - q +1
> you get
> phi = n - p - n/p +1
>
> multiply by p
> p*phi = n*p - p^2 - n + p
>
> this gives the quadratic equation:
> p^2 + (phi - n - 1)*p +n = 0
>
> you can solve this equation by any real square root approximation (e.g.
> Newton) and round to the nearest integer.

?? it MUST be an integer. If you have to "round" you have the wrong
answer.

>
> BTW, this algorithm will not work in case ed = 1 is only defined mod
> lcm(p-1,q-1)
>
>
> Best Regards,
> Rainer
>
>
>
> "Mok-Kong Shen" <mok-kong.shen(a)t-online.de> schrieb im Newsbeitrag
> news:hk1p2a$t1t$03$1(a)news.t-online.com...
>> Rainer Urian wrote:
>>
>>> Calculating p,q from n,e,d is simple if de = 1 mod phi(n). It is merely
>>> solving a quadratic equation in Z.
>>
>> Could you please tell how to do that by solving one (single) quadratic
>> equation in Z?
>>
>> Thanks,
>>
>> M. K. Shen
>>
>
From: Mok-Kong Shen on 30 Jan 2010 14:48
unruh wrote:
> Rainer Urian wrote:
>> here you are!
>>
>> we start by
>> e*d == 1 mod phi(n)
>>
>> this means
>> e*d = 1 + k*phi(n)
>>
>> first one must determine k:
>> since one can assume p and q are much smaller than n, one can calculate
>> k = ceil((e*d-1) /n) //ceil = next greatest integer
>
> Nope. This may work is e is very very small ( eg 3) but not for
> moderately large ea and certainly not if you choose d>n
> If e is very small, and d is the smallest solution of ed-1=0 mod(p-1)(q-1).

Why should one employ a d>n? If a d>n were used, doesn't d1 = d mod n
serve the purpose just as well as d in the present context?

Anyway, one has:

e*d - 1 = k * (p-1)*(q-1) = k * (N - p - q + 1)

With the assumption stated in the quote, the equation for k follows.

M. K. Shen

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Method and Logic
Next: Frustration with mathematics