Implementation of RSA and One-Way Permutations

Cryptography CS5830 - Jake Magid - [email protected]

Usage

The file can be called from the terminal as python oneway.py and will generate x, f(x), and x_ret using RSA implementation and trapdoor. This will also print a safe prime number with n_in bits. Change this value as necessary.

Other functions can be tested in the Print Section of the code by uncommenting them and manipulating the inputs as necessary.

Functions and Classes

• Extended Euclid
  extendedeuclid(a,b)
  Input: Two values a and b
  Output: x,y such that ax + by = 1

• Inverse Modulus
  inv_mod(a,b)
  Input: Two values a and b
  Output: Modular inverse of a mod b (i.e. x such that ax mod b = 1)

• Exponential Modulus
  exp_mod(a,x,N)
  Input: Values a, x, N
  Output: a^x mod N

• Miller-Rabin Primality Test
  is_prime(n)
  Input: odd integer n to be tested for primality
  Output: True if number is probably prime, False if number is composite

• Random n-bit Prime
  rand_nbit_prime(n)
  Input: max number of bits n which prime number can be represented by
  Output: random prime integer that can be represented using n bits

• Random n-bit Safe Prime
  rand_nbit_safe_prime(n)
  Input: number of bits to find a safe prime n
  Output: p, an n-bit safe prime and q, the corresponding Sophie Germain prime

• Random n-bit Safe Prime Generator
  rand_nbit_safe_prime_generator(n)
  Input: number of bits to find a safe prime n
  Output: p, an n-bit safe prime and g, a generator for Z_p*

• Exponentiation One Way Permutation
  class exponentiation_OWP

  • gen(n)
    Input: number of bits n
    Output: p, an n-bit safe prime and g, a generator for Z_p*

  • sample(p)
    Input: p from gen()
    Output: x, a random integer from 1 to p-1

  • evaluate(p,g,x)
    Input: p,g,x from gen() and sample()
    Output: fx which is g^x mod p

• RSA One Way Permutation
  class RSA_OWP

  • gen(n)
    Input: number of bits n for p and q
    Output: The public keys N,e and the private trapdoor key d.
    N is p*q. e is a random integer from 2 to phi-1 where phi = (p-1)*(q-1). d is the inverse modulus of e and phi.

  • sample(N)
    Input: N from gen()
    Output: x, a random integer from 1 to N

  • evaluate(x,e,N)
    Input: x,e,N from gen() and sample()
    Output: fx which is x^e mod N

• Trapdoor for RSA
  trapdoor(fx, d, N)
  Input: fx, d, N from RSA_OWP.gen(), RSA_OWP.sample(), and RSA_OWP.evaluate()
  Output: The corresponding x that produced fx. The magic here is that x can be retrieved from fx using the public information N, and the private key d.