Re: Idea for the Schmidt-Samoa PK algorithm



Tom St Denis <tom@xxxxxxx> wrote:
I'm writing a wiki article about [among other things] the Schmidt-
Samoa algorithm which works as follows

1. compute two large primes p and q and N = p^2q
2. compute d == 1/N mod lcm(p-1,q-1)

Your public key is N and your private key is (d, pq)

to encrypt

c = m^N mod N

and decrypt

m = c^d mod pq

However, could you not also compute

e = N mod lcm(p-1,q-1)

and then use (N, e) as the public key?

So I guess the question is does revealing the reduced value of 'e'
compromise the system? My hunch is yes since N is known you're
basically now solving for N - a*phi(pq) = e giving

N - e = a*phi(pq)

Suppose I have a multiple t of (p-1)(q-1). Now take a random integer x
relatively prime to N and raise it to the t'th power modulo N. It is now
congruent to 1 modulo pq, but most likely not congruent to 1 modulo N.
Hence, gcd(x^t-1, N) will most likely be pq. Hence, we get p = N /
gcd(x^t-1, N).

In the same way, we get that the one-way-ness of the system is equivalent
to factoring integers of the form p^2q (which _might_ be easier than
factoring integers of the form pq). Take any x, compute c = x^N mod N,
get an N'th root y of c modulo N, with overwhelming probability, x !=
y and then we get p = N / gcd(x-y, N).

--
kg
.



Relevant Pages

  • Re: Ponder on this.
    ... The public key is a product of two large primes. ... Those two large numbers are important in that have been carefully tested for primality: by construction having no small factors <N for some modest N and also satisfying Fermats little theorem for several test primes. ... I would not rely on 128bit encryption for anything I really cared about keeping secret. ...
    (sci.electronics.design)
  • Need a bit help with decyphering a message
    ... not tell the encryption algorithm, so I decided to do a little ... I checked dozens of packets, and found out that the first 8 bytes are ... It is likely that they are primes, ... if it would be a Public Key). ...
    (sci.crypt)
  • Re: Need a bit help with decyphering a message
    ... which was "attila". ... not tell the encryption algorithm, so I decided to do a little ... It is likely that they are primes, ... if it would be a Public Key). ...
    (sci.crypt)
  • Re: How to detect RSA keys that are weak?
    ... generating primes from a set of prescribed size N(surely obvious to ... feed it to a PRNG, and use this PRNG to tentatively generate primes of ... The trick with the public key is more interesting. ...
    (sci.crypt)
  • Re: Towards a Formula for Primes
    ... they got themselves a giant computer. ... There are two primes. ... public key, which anybody can use for coding. ... on irrationality. ...
    (sci.math)