Idea for the Schmidt-Samoa PK algorithm
in [Cryptography]
|
From: Tom St Denis on 4 Aug 2010 06:30 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) Where 'a' is likely to be factored out easily enough (it could be as large as ~min(p,q)) .... Tom
From: biject on 4 Aug 2010 09:37 On Aug 4, 4:30 am, Tom St Denis <t...(a)iahu.ca> 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) > > Where 'a' is likely to be factored out easily enough (it could be as > large as ~min(p,q)) .... > > Tom If its only a question of giving your enemy an extra piece of info then the answer is give as little info as possible. However it seems like in the method you are using N = p^2q so why give an e that would be stupid. However if using RSA N = pq which is apples a oranges. Since you need the e If your going to use N and e why not stick to RSA Also if the RSA N and the SS N the same size the RSA N is more secure in that the p and q could be larger for the same space. p^2q versus pq If the pq are the same size I would guess the SS method safer for now. However some clever Chinese person might be able to find a clever fast method to factor such a form easily. the SS method almost looks like you are using RSA where N = pq and e = p. David A. Scott -- My Crypto code http://bijective.dogma.net/crypto/scott19u.zip http://www.jim.com/jamesd/Kong/scott19u.zip old version My Compression code http://bijective.dogma.net/ **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
From: Tom St Denis on 4 Aug 2010 11:11 On Aug 4, 9:37 am, biject <biject.b...(a)gmail.com> wrote: > On Aug 4, 4:30 am, Tom St Denis <t...(a)iahu.ca> 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) > > > Where 'a' is likely to be factored out easily enough (it could be as > > large as ~min(p,q)) .... > > > Tom > > If its only a question of giving your enemy an extra piece of info > then the answer is give as little info as possible. > > However it seems like in the method you are using > N = p^2q > so why give an e that would be stupid. Because 'e' is smaller than N, if it weren't insecure it'd be a good idea. > However if using RSA > N = pq which is apples a oranges. Since you need > the e > > If your going to use N and e why not stick to RSA SS is reducible to factoring, RSA is not. > Also if the RSA N and the SS N the same size the > RSA N is more secure in that the p and q could be > larger for the same space. p^2q versus pq True, presumably for same size N you'd need p and q large enough to avoid ECM factoring. Tom
From: Kristian Gj�steen on 4 Aug 2010 18:40 Tom St Denis <tom(a)iahu.ca> 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
|
Pages: 1 Prev: Finding out how secure a cipher is Next: Last CFP - Applied Computing 2010: 3 September 2010 |