[wrong][spam] Cracking PGP

Karl gmkarl at gmail.com
Fri Jun 18 10:58:13 PDT 2021


Here's the key generation section from the Wikipedia article.  It's hard to
move my body toward this.

===Key generation===
The keys for the RSA algorithm are generated in the following way:
# Choose two distinct [[prime number]]s ''p'' and ''q''.
#* For security purposes, the integers ''p'' and ''q'' should be chosen at
random, and should be similar in magnitude but differ in length by a few
digits to make factoring harder.<ref name="rsa"/> Prime integers can be
efficiently found using a [[primality test]].
#* ''p'' and ''q'' are kept secret.
# Compute {{nowrap|1=''n'' = ''pq''}}.
#* ''n'' is used as the [[Modular arithmetic|modulus]] for both the public
and private keys. Its length, usually expressed in bits, is the [[key
length]].
#* ''n'' is released as part of the public key.
# Compute ''λ''(''n''), where ''λ'' is [[Carmichael's totient function]].
Since ''n'' = ''pq'', ''λ''(''n'') = [[least common
multiple|lcm]](''λ''(''p''),''λ''(''q'')), and since ''p'' and ''q'' are
prime, ''λ''(''p'') = ''[[Euler totient function|φ]]''(''p'') = ''p'' − 1
and likewise ''λ''(''q'') = ''q'' − 1. Hence ''λ''(''n'') = lcm(''p'' − 1,
''q'' − 1).
#* ''λ''(''n'') is kept secret.
#* The lcm may be calculated through the [[Euclidean algorithm]], since
lcm(''a'',''b'') = ''|ab|''/gcd(''a'',''b'').
# Choose an integer ''e'' such that {{nowrap|1 < ''e'' < ''λ''(''n'')}} and
{{nowrap|1=[[greatest common divisor|gcd]](''e'', ''λ''(''n'')) = 1}}; that
is, ''e'' and ''λ''(''n'') are [[coprime]].
#* ''e'' having a short [[bit-length]] and small [[Hamming weight]] results
in more efficient encryption {{snd}} the most commonly chosen value for
''e'' is {{nowrap|1=2<sup>16</sup> + 1 = 65,537}}. The smallest (and
fastest) possible value for ''e'' is 3, but such a small value for ''e''
has been shown to be less secure in some settings.<ref name="Boneh99">
{{cite journal
 | url = http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html
 | last = Boneh | first = Dan
 | title = Twenty Years of attacks on the RSA Cryptosystem
 | journal = [[Notices of the American Mathematical Society]]
 | volume = 46 | issue = 2
 | pages = 203–213 | year = 1999
}}</ref>
#*''e'' is released as part of the public key.
# Determine ''d'' as {{nowrap|''d'' ≡ ''e''<sup>−1</sup> (mod
''λ''(''n''))}}; that is, ''d'' is the [[modular multiplicative inverse]]
of ''e'' modulo ''λ''(''n'').
#* This means: solve for ''d'' the equation {{nowrap|''d''⋅''e'' ≡ 1 (mod
''λ''(''n''))}}; ''d'' can be computed efficiently by using the [[Extended
Euclidean algorithm]], since, thanks to ''e'' and ''λ''(''n'') being
coprime, said equation is a form of [[Bézout's identity]], where ''d'' is
one of the coefficients.
#* ''d'' is kept secret as the ''private key exponent''.
The ''public key'' consists of the modulus ''n'' and the public (or
encryption) exponent ''e''. The ''private key'' consists of the private (or
decryption) exponent ''d'', which must be kept secret. ''p'', ''q'', and
''λ''(''n'') must also be kept secret because they can be used to calculate
''d''. In fact, they can all be discarded after ''d'' has been
computed.<ref>Applied Cryptography, John Wiley & Sons, New York, 1996.
[[Bruce Schneier]], p. 467</ref>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 5479 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20210618/b2a5bad8/attachment.txt>


More information about the cypherpunks mailing list