About RSA-HSD and RSA-HP

[Dark-Avenger]

Why RSA-HSD and RSA-HP keys can't be distingued from trusted RSA key generator ?

[data]

hi,

I doubt that it is a true statement. There are ways to verify a black box

Have a look at the following url's

http://www.mail-archive.com/cypherpunks@minder.net/msg27598.html

http://www.google.co.in/search?q=cache:XpQ2jtDbOyQJ:cnx.rice.edu/content/m11901/latest/+logical+analyzer&hl=en

The main url seems to be down, hence I have posted the equivalent google cache. I am not much into electronics though I just undertstand the basic idea from the definition.

Data.
_________________
"It looked absolutely impossible.But it so happens that you go on worrying away at a problem in science and it seems to get tired,and lies down and lets you catch it."-William Lawrecne Bragg.

[Dark-Avenger]

Interesting post Datah, but after another read of article, i think that i understood why it's hard to detect the bias. I will try to explain it with RSA-HSD (HSD = Hidden Small Decryption exponent) algorithm (others are only variants):

RSA-HSD generates an RSA key with t bits and a backdoor number b:

1. generate two primes p and q with t/2 bits
2. generate an odd number o with less than t/4 bits, prime with phi(n) = (p-1)(q-1)
3. compute (psi = o^-1 mod phi(n)) and (e = b xor psi)
4. while gcd(e, phi(n)) is not equal to 1 do again 2. and 3.
5. compute (d = e^-1 mod phi(n))
6. return (p*q, e, d)

Exploiting generated keys:

1. compute (psi = e xor b)
2. compute o using Wiener's attack
3. factorize n using psi and o
4. compute d using e and factorization of n

The only change between a trusted RSA key generator and RSA-HSD is etaps 3 and 4 which cost is very low behind the cost of generation of p, q and p*q, so we can't find RSA-HSD using time generation.

The randomness of o and properties of xor make impossible to deduce from e that e = psi xor b if we don't know b. I think it is the reason why we can't distingued a trusted RSA key from a RSA-HSD key.

Cheers

[data]

Now I know too. Thank you!
_________________
"It looked absolutely impossible.But it so happens that you go on worrying away at a problem in science and it seems to get tired,and lies down and lets you catch it."-William Lawrecne Bragg.