／var／logmarcus chiu

Rivest, Shamir, & Adleman (RSA) Algorithm

Created on Β· Last Modified on

Rivest, Shamir, & Adleman (RSA) Algorithm

RSA - Introduction

RSA Creation Steps

Using modular exponentiation for encryption
  • π‘šπ‘’ π‘šπ‘œπ‘‘ 𝑁 ≑ 𝑐

Given π‘š, 𝑒, 𝑁 it is EASY to compute 𝑐 (encrypting π‘š)

  • π‘šπ‘’ π‘šπ‘œπ‘‘ 𝑁 ≑ ?

Given 𝑐, 𝑒, 𝑁 it is HARD to compute π‘š (decrypting 𝑐)

  • ?𝑒 π‘šπ‘œπ‘‘ 𝑁 ≑ 𝑐
Determine what is needed for decryption

Find 𝑑 to β€œundo” 𝑒

  • π‘šπ‘’ π‘šπ‘œπ‘‘ 𝑁 ≑ 𝑐
  • 𝑐𝑑 π‘šπ‘œπ‘‘ 𝑁 ≑ π‘š

With modular arithmetic the 2 equations above result in:

  • π‘šπ‘’π‘‘ π‘šπ‘œπ‘‘ 𝑁 ≑ π‘š

The problem is figuring out what value to choose for 𝑒 and 𝑑

Introducing phi function 𝛷(𝑁)

𝛷(𝑛) is the number of integers π‘˜ in the range 1 ≀ π‘˜ ≀ 𝑛 for which the greatest common divisor 𝑔𝑐𝑑(𝑛, π‘˜) is equal to 1.

  • 𝛷(π‘ π‘œπ‘šπ‘’-π‘›π‘’π‘šπ‘π‘’π‘Ÿ) is HARD to compute
  • 𝛷(π‘π‘Ÿπ‘–π‘šπ‘’-π‘›π‘’π‘šπ‘π‘’π‘Ÿ) is EASY to compute, 𝛷(π‘π‘Ÿπ‘–π‘šπ‘’-π‘›π‘’π‘šπ‘π‘’π‘Ÿ) = π‘π‘Ÿπ‘–π‘šπ‘’-π‘›π‘’π‘šπ‘π‘’π‘Ÿ - 1
  • 𝛷(π‘Ž * 𝑏) = 𝛷(π‘Ž) * 𝛷(𝑏)

Choosing 𝑁 to be equal to π‘π‘Ÿπ‘–π‘šπ‘’-π‘œπ‘›π‘’ * π‘π‘Ÿπ‘–π‘šπ‘’-π‘‘π‘€π‘œ, then:

  • 𝛷(𝑁) = 𝛷(π‘π‘Ÿπ‘–π‘šπ‘’-π‘œπ‘›π‘’) * 𝛷(π‘π‘Ÿπ‘–π‘šπ‘’-π‘‘π‘€π‘œ)

Thus, 𝛷(𝑁) is EASY to compute when its prime-factorization (i.e. π‘π‘Ÿπ‘–π‘šπ‘’-π‘œπ‘›π‘’ * π‘π‘Ÿπ‘–π‘šπ‘’-π‘‘π‘€π‘œ) is known. The prime-factorization of large 𝑁 is HARD to compute.

Merging 𝛷(𝑁) with modulo exponentiation

Euler’s theorem states, for any π‘š,𝑛, and gcd(π‘š,𝑛) = 1 then:

  • π‘šπ›·(𝑛) ≑ 1 π‘šπ‘œπ‘‘ 𝑛

Rearranging Euler’s theorem with modular arithmetic:

  • π‘šπ›·(𝑛)π‘˜ ≑ 1π‘˜ π‘šπ‘œπ‘‘ 𝑛
  • π‘šπ›·(𝑛)π‘˜ ≑ 1Β π‘šπ‘œπ‘‘ 𝑛
  • π‘šΒ·π‘šπ›·(𝑛)π‘˜ ≑ π‘šΒ·1 π‘šπ‘œπ‘‘ 𝑛
  • π‘šπ›·(𝑛)π‘˜+1 ≑ π‘š π‘šπ‘œπ‘‘ 𝑛

Now we have modulo exponentiation that depends on 𝛷(𝑁)!

Thus, the values for 𝑒 and 𝑑:

  • 𝑑 = [𝛷(𝑛)π‘˜+1] / 𝑒

RSA - Usage

Algorithm

Example

private-public key pair - setup:

  • select two large prime numbers, p and q
  • n = pq
  • z = (p-1)(q-1)
  • select a number e:
    • 1 < e < z
    • e is a prime relative to z (e and z have no common factors, except 1)
  • select a number d:
    • ((e*d) - 1) is divisible by z (i.e. ed mod z = 1)
  • the public key is: (e, n)
  • the private key is: (d, n)

private-public key pair - encryption/decryption:

  • a message m (m<n) is encrypted as cipher-text c:
    c = memod n
  • a cipher-text c is decrypted as follows:
    m = cd mod n

private-public key pair - setup:

  • select primes: p=17 & q=11
  • n = pq = 17 x 11 = 187
  • z = (p–1)(q-1) =16 x 10 = 160
  • select a number e:
    • 1 < e < 160
    • gcd(e,160) = 1
  • e = 7
  • select a number d:
    • ((e*d) - 1) is divisible by z
    • (e*d) - 1 = z
    • (7*d) = 161
    • d = 23
  • d = 23
  • the public key is: (e=7, n=187)
  • the private key is: (d=23, n=187)

private-public key pair - encryption/decryption:

  • encrypt message: m = 55
    c = memod n
    c = 557 mod 187
    c = 132
  • decrypt cipher-text: c = 132
    m = cd mod n
    m = 13223 mod 187 (use wolfram alpha)
    m = 55