Prev: Method and Logic
Next: Frustration with mathematics
From: Mok-Kong Shen on 2 Feb 2010 04:19
Mok-Kong Shen:
> 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.

I mean:

ed - 1 = k * lcm(p-1,q-1)

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

All prime factors of phi(n) are also in lcm(p-1,q-1) and hence form
a subset of those of ed-1. Thus, if ed-1 is not hard to factor, one
can solve for p and q, since the number of candidates of phi(n) is
finite.

M. K. Shen

From: amzoti on 2 Feb 2010 11:02
On Jan 30, 9:56 am, unruh <un...(a)wormhole.physics.ubc.ca> wrote:
> On 2010-01-30, Rainer Urian <rai...(a)urian.eu> wrote:
>
> > 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?
>


http://acronyms.thefreedictionary.com/CRT

However, I think it is a safe bet to go with this one:
http://mathworld.wolfram.com/ChineseRemainderTheorem.html

;-)
From: Rainer Urian on 3 Feb 2010 23:59
the problem is that you cannot know if ed-1 is simple to factor.For
instance, if p,q are Germain primes (i.e. p'= (p-1)/2 is also prime) then
you cannot factor 2*p'*q'. You also cannot know that lcm and phi differ only
by a factor of 2.
On the other hand, before using an algorithm which needs factoring, it is
far more preferable to use a fast probabilistic algorithm.

Rainer



"Mok-Kong Shen" <mok-kong.shen(a)t-online.de> schrieb im Newsbeitrag
news:hk8qnn$poj$00$1(a)news.t-online.com...
> Mok-Kong Shen:
>> 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.
>
> I mean:
>
> ed - 1 = k * lcm(p-1,q-1)
>
> phi(n) <= lcm(p-1,q-1)^2 <= (ed - 1)^2
>
> All prime factors of phi(n) are also in lcm(p-1,q-1) and hence form
> a subset of those of ed-1. Thus, if ed-1 is not hard to factor, one
> can solve for p and q, since the number of candidates of phi(n) is
> finite.
>
> M. K. Shen
>

From: Francois Grieu on 4 Feb 2010 13:02
Rainer Urian wrote:

> 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

[nitpicks: these are requirement for d, not definitions of d,
much less of RSA]

A most usual definition of d, that in PKCS#1, is

The RSA private exponent d is a positive integer less
than n satisfying (2).

This leaves the choice open for at least two distinct d. It is very
common that the smallest d is chosen, and that it does not verify (1).
Therefore assuming (1) is bad.

ANSI X9.31 asks for (2) and puts a lower bound on d, which can only
be meaningfully interpreted as requiring that d is less than
lcm(p-1,q-1), and similarly (1) can't be assumed.

Actually I fail to locate of any specification which requires (1).


Francois Grieu
From: Mok-Kong Shen on 5 Feb 2010 04:09
Rainer Urian wrote:
> the problem is that you cannot know if ed-1 is simple to factor.For
> instance, if p,q are Germain primes (i.e. p'= (p-1)/2 is also prime) then
> you cannot factor 2*p'*q'. You also cannot know that lcm and phi differ
> only by a factor of 2.
> On the other hand, before using an algorithm which needs factoring, it
> is far more preferable to use a fast probabilistic algorithm.

But a fast probabilistic algorithm on what (not to factor something?) ?

Thanks,

M. K. Shen

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