Re: RSA Private Key representation

Kristian Gjøsteen wrote:
Kristian Gjøsteen <kristiag+news@xxxxxxxxxxxx> wrote:
Giuliano Bertoletti <gbe32241@xxxxxxxxx> wrote:
I was wondering if it's mathematically easy to go back and forth from the canonical RSA private key representation (modulus + private exponent) to the CRT form (PRIME_1, PRIME_2, COEFFICIENT, EXP_1, EXP_2).
Use the secret exponent to factor the modulus.

Ouch, that had too many mistakes. Let me do it more carefully.

If you can factor the modulus, then you can get to the CRT form. We can
factor the modulus if we have the public key (n,e) and the private key
(n,d).

Let n=pq. Modulo n, we have four square roots of one, 1, -1, and two
more, call them x and y. We can call them non-trivial square roots of
one. We know that x and y must be +- 1 modulo p and q, so suppose x =
1 (mod p), x = -1 (mod q). Then x-1 = 0 (mod p) and x-1 != 0 (mod q).
In other words, p divides x-1, but q does not divide x-1. This means
that gcd(x-1,n) = p.

Conclusion: if we can find a non-trivial square root of one modulo n,
we can factor n.

We know that ed = 1 (mod (p-1)(q-1)).

No, ed mod (p-1)(q-1) may be a multiple of gcd(p-1, q-1).
You know that ed = 1 mod p-1 and that ed = 1 mod q-1, from which you may conclude ed = 1 mod lcm(p-1, q-1).

In other words, (p-1)(q-1) divides
ed-1. Modulo n, every invertible element has order dividing (p-1)(q-1).

Write ed - 1 = 2^t s, where s is odd. Let a be invertible modulo n.
Then we know that a^(ed-1) = 1 (mod n). Find the smallest i such that
a^(2^i s) = 1 (mod n). If i>0, then 2^(2^(i-1) s) is a square root of
one modulo n. Approximately half of all a will result in a non-trivial
square root of one in this manner.

In other words, write ed - 1 = 2^t s, s - odd. Choose a random a, find the
smallest i such that a^(2^i s) = 1 (mod n). If i>0 and a^(2^(i-1) s) is
a non-trivial square root of one modulo n, factor n as above. Otherwise,
try a new a.

--Mike Amling

--
Posted via NewsDemon.com - Premium Uncensored Newsgroup Service
------->>>>>>http://www.NewsDemon.com<<<<<<------
Unlimited Access, Anonymous Accounts, Uncensored Broadband Access
.

Relevant Pages

  • Re: RSA Private Key representation
    ... Use the secret exponent to factor the modulus. ... factor the modulus if we have the public key and the private key ... Modulo n, we have four square roots of one, 1, -1, and two ... if we can find a non-trivial square root of one modulo n, ...
    (sci.crypt)
  • Re: Rabin vs. RSA/ElGamal
    ... roots for me modulo your modulus, ... But then, so is "raw RSA". ... permutation into a full-blown public-key encryption scheme. ... or cubing modulo N -- a building block, not something it makes sense to ...
    (sci.crypt)
  • Re: RSA .crt and .key file formats?
    ... > and private key file (actually, the private key file, from what I can ... Basically, for RSA signatures, and for RSA decryption, you need to ... needs only the modulus n and the private exponent d. ... setting is to choose a random binary value K, encrypt it ...
    (sci.crypt)
  • Re: Is there any COBOL program for verify the SSN?
    ... Modulus 11 is NOT the same as Modulo 11. ... The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. ...
    (comp.lang.cobol)
  • Re: [QUIZ] Modular Arithmetic (#179)
    ... one less than the modulus. ... we must use the appropriate congruent value modulo 24. ... While most operations will be straightforward, modular division is a ... def coerce ...
    (comp.lang.ruby)
Quantcast