Math 2.0

Information and communication theory, circuits Example

RSA cryptosystem

Builds on Euler's theoremEuler's totient functionModular multiplicative inverseModular exponentiation

Example

The RSA cryptosystem is an example of public-key cryptography. To make the keys, choose two distinct primes pp and qq, and put n=pqn = pq and φ(n)=(p−1)(q−1)\varphi(n) = (p - 1)(q - 1), the value of Euler's totient function. Choose an integer ee with 1<e<φ(n)1 < e < \varphi(n) and gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1. Let dd be the inverse of ee modulo φ(n)\varphi(n). The public key is (n,e)(n, e), and the private key is dd. To encrypt a message mm with 0≤m<n0 \le m < n, compute c=me mod nc = m^e \bmod n. To decrypt, compute cd mod nc^d \bmod n, which is equal to mm. A small case: p=5p = 5, q=11q = 11, n=55n = 55, φ(n)=40\varphi(n) = 40, e=3e = 3 and d=27d = 27, since 3⋅27=81≡1(mod40)3 \cdot 27 = 81 \equiv 1 \pmod{40}. The message m=2m = 2 gives c=23=8c = 2^3 = 8, and 827≡2(mod55)8^{27} \equiv 2 \pmod{55}.

Remarks

Decryption works by Euler's theorem: ed=1+kφ(n)ed = 1 + k \varphi(n), so med≡m(modn)m^{ed} \equiv m \pmod n when gcd⁡(m,n)=1\gcd(m, n) = 1. The general case follows from the Chinese remainder theorem. The security rests on the belief that it is hard to factor nn when pp and qq are large. Ron Rivest, Adi Shamir and Leonard Adleman described the system publicly in 1977.

Reading path

To understand this page from the ground up, read these 9 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionModular exponentiation, concept, no evidence levelModular exponentiationconceptCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionGreatest common divisor, definition, no evidence levelGreatest common divis…definitionModular multiplicative inverse, definition, no evidence levelModular multiplicativ…definitionCoprime integers, definition, no evidence levelCoprime integersdefinitionEuler's totient function, definition, no evidence levelEuler's totient funct…definitionEuler's theorem, statement, no evidence levelEuler's theoremstatementRSA cryptosystem, example, no evidence levelRSA cryptosystemexample
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Modular exponentiation concept
  3. Congruence modulo n definition
  4. Greatest common divisor definition
  5. Modular multiplicative inverse definition
  6. Coprime integers definition
  7. Euler's totient function definition
  8. Euler's theorem statement
  9. RSA cryptosystem example

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/RSA_cryptosystem, Key generation
  2. Web https://en.wikipedia.org/wiki/RSA_cryptosystem, Proof using Euler's theorem
About this page
Tag0HM584C465
URIm2://0HM584C465
Aliasesrivest-shamir-adleman
Kindexample
WritingW2 usable
MSC94A60
Instance ofPublic-key cryptography
UsesEuler's theorem, Euler's totient function, Modular multiplicative inverse, Modular exponentiation
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W3

  • a person confirmed each agent-written section: rule P04 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by