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 |