Prev: Method and Logic
Next: Frustration with mathematics
From: Rainer Urian on 30 Jan 2010 15:41
> 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).

it works with typical RSA parameters.
One can calculate the exact bounds

>> Then one can calculate phi by
>> phi = (e*d-1)/k
>
> Nope.
This is a consequence of the previous statement

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

Nope :-)
If you KNOW, the answer MUST be in Z , than you can approximate it. The next
nearest Integer MUST be the correct solution.


BTW,
are you addicted to Nope ?




From: Mok-Kong Shen on 30 Jan 2010 17:07
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.
> But calculating p,q from if de = 1 mod lcm(p-1,q-1) is rather more
> involved. One needs a probabilistic algorithm (which I don't know its
> name but I think its folklore knowledge)

You have explained in a post the computation for the case of
mod phi(n). If I don't err, the same technique could also work for
the case of mod lcm(p-1,q-1) as follows:

lcm(p-1,q-1)^2 = c * phi(n) for a certain c. From

de - 1 = k * lcm(p-1,q-1) one has

(de -1)^2 = (k^2 * c) * phi(n) = k' * phi(n)

which is an equation akin to the case of mod phi(n).

M. K. Shen
From: Rainer Urian on 31 Jan 2010 06:15
No, this will not work.
The approximation of (ed-1)/phi(n) by ceil((ed-1)/n) works only as long as
ed-1 is not too big.
For instance, if q is the smaller prime and d < phi(n), than the formula is
correct for
e < q/2, i.e. ed-1 < q/2*phi(n)

But in your case , (ed-1)^2 > phi(n)^2 >> q/2*phi(n) and therefore the
formula breaks down.




"Mok-Kong Shen" <mok-kong.shen(a)t-online.de> schrieb im Newsbeitrag
news:hk2ai3$mkq$02$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.
>> But calculating p,q from if de = 1 mod lcm(p-1,q-1) is rather more
>> involved. One needs a probabilistic algorithm (which I don't know its
>> name but I think its folklore knowledge)
>
> You have explained in a post the computation for the case of
> mod phi(n). If I don't err, the same technique could also work for
> the case of mod lcm(p-1,q-1) as follows:
>
> lcm(p-1,q-1)^2 = c * phi(n) for a certain c. From
>
> de - 1 = k * lcm(p-1,q-1) one has
>
> (de -1)^2 = (k^2 * c) * phi(n) = k' * phi(n)
>
> which is an equation akin to the case of mod phi(n).
>
> M. K. Shen

From: Mok-Kong Shen on 1 Feb 2010 07:11
Rainer Urian wrote:
> No, this will not work.
> The approximation of (ed-1)/phi(n) by ceil((ed-1)/n) works only as long
> as ed-1 is not too big.
> For instance, if q is the smaller prime and d < phi(n), than the formula
> is correct for
> e < q/2, i.e. ed-1 < q/2*phi(n)
>
> But in your case , (ed-1)^2 > phi(n)^2 >> q/2*phi(n) and therefore the
> formula breaks down.

Here is a second trial, though offhand I can't know how practical it is:

lcm(p-1,q-1) <= phi(n) <= lcm(p-1,q-1)^2

lcm(p-1,q-1) contains all (and only) the prime factors in phi(n).
Assuming it is not hard to factorize, one has a finite number of
candidates for phi(n). With

phi(n) = n - p - q + 1

n = p * q

one can solve for p and q.

M. K. Shen
From: Mok-Kong Shen on 1 Feb 2010 09:44
Mok-Kong Shen wrote:

> Here is a second trial, though offhand I can't know how practical it is:
[snip]

Apology, my big mistake: lcm(p-1,q-1) is unknown. But there might be
certain non-negligible chance of employing the factors of ed-1 that
way, I guess.

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