Maybe clean it up some On Fri, Jun 18, 2021, 2:00 PM Karl <[email protected]> wrote:
> I'll go through it a little. > > On Fri, Jun 18, 2021, 1:58 PM Karl <[email protected]> wrote: > >> ===Key generation=== >> The keys for the RSA algorithm are generated in the following way: >> # Choose two distinct [[prime number]]s ''p'' and ''q''. >> > > #* ''p'' and ''q'' are kept secret. >> # Compute 'n'' = ''pq'' >> > > public n = private p * private q > n is keylength bits long. > > # Compute ''λ''(''n''), where ''λ'' is Carmichael's totient function. >> Since ''n'' = ''pq'', ''λ''(''n'') = lcm(''λ''(''p''),''λ''(''q'')), and >> since ''p'' and ''q'' are prime, ''λ''(''p'') = ''φ''(''p'') = ''p'' − 1 >> where φ is the Euler totient function, and likewise ''λ''(''q'') = ''q'' >> − 1. Hence ''λ''(''n'') = lcm(''p'' − 1, ''q'' − 1) >> > > private lambda(n) is calculated and has a number of relevant algebraic > identities associated > > #* The lcm may be calculated through the Euclidean algorithm, since >> lcm(''a'',''b'') = ''|ab|''/gcd(''a'',''b''). >> # Choose an integer ''e'' such that 1 < ''e'' < ''λ''(''n'') and >> gcd(''e'', ''λ''(''n'')) = 1; that is, ''e'' and ''λ''(''n'') are coprime. >> > Organised a little up to here. #* ''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> >> >
