So, this essay is finally done...after blowing of the dust from the introduction, that was
written five months ago.
For all those of you that enjoy studying chiphers, I'm now happy to present to you
....."A true RSA story!"
Time has been my enemy, and that's the reason for working on this essay so long.

What can I say? So much to do, so little time!

This essay contains alot of mathematical theorys that one must grasp in order to understand
how the RSA algorithm works. If you don't understand them while reading this essay, I
recommend that you pick up a math realated book and study them, so that you can focus on
the real issue of this paper.

One-way function

Some time ago the main goal when designing cryptosystems, was to make the encryption function
as complicated as possible, with the belive that this would imply security. But Diffie and Hellman
was the first to notice the importance of basing cryptography on some kind of provable security
with respect to computational complexity, and in particular, one-way functions.
Sadly it's unknown if such function exist, but we'll assume that it does, since this field basically
breaks down without one-way functions.
The RSA encryption has the public-key property, anyone can encrypt, but only the intended can
decrypt it.

Hard-core bits

A asked B a question and B wants to send a yes or a no to A as an answer, and C knows that
the message from B contains either a yes or a no. C could now encrypt both possibilities and
compare them to the intercepted cryptogram from B.
A and B has without considering possible vulnerabilities now agreed on the following:
A chooses a completely random integer x and sends the encryption f (2x) if the answer is yes, and
f (2x+1) if it's no. B then checks if the message was odd or even, after decryption.
Now it's hopeless for C to encrypt all messages corresponding to an odd or even number, however
if f  leaks information on the odd or even bit, C can still find out the answer.
So what can we conclude?
Well, it's important to identify the secure part of the message (if any).
Using a key that's shorter then the encrypted message enables the adversary to obtain information
regarding the message. Goldwasser and Micali came up with a solution to this problem in 1984,
they constructed a probabilistic encryption scheme which is guaranteed to hide all plaintext.
The probabilistic encryption scheme is however based on stronger assumptions then just the
existence of one-way functions.

Introduction to RSA

RSA is one of the most popular public key ciphers. In RSA one key is used to encrypt data
and an other to decrypt it, RSA is asymmetric.
RSA is a block cipher, but the size of the block varies depending on the size of the keys.
If the amount of data to be encrypted is not an even multiple of this size, it's padded in some
application-specific way. RSA is considered very secure, but the security has never been
proven. It's related to the difficult problem of factoring large numbers, and since no efficient
solutions are known for this, it's assumed that there are no afficient ways to crack RSA encryption.

When transmitting data across a network their is no need of transmitting the key used to
encrypt the data. This is an important implication of RSA since the risk of getting the key
compromised reduces.
When encrypting data we'll use a key which is considered public, while those allowed to
decrypt this data uses a second key, which is private.

Encrypting and decrypting data with RSA revolves around modular exponentiation, an
operation in modular arithmetic.
 
 
 

 
 
Modular arithmetic

The theory of modular arithmetic is that only the numbers which are non-negative integers less
then the modulus is under consideration. In other words, modular arithmetic is integer arithmetic
as usual except that when we work modulo n, every result x is replaced with a member of
{0,1......., n-1} so that x mod n is the reminder of x/n.
If two numbers product equals 1, we say that they are the modular inverse of each other.

Ex.

      (11+16) mod12 = 3
 
      (2 * 9) mod13 = 5
 
 

Euler's phi-function

This function f, defines how many numbers less then n are relative prime with n.
Two numbers are relative prime if they share only one factor, 1 (e.g. 10 and 21). This leads
us to the first relevant property, namely:
 

• When n is prime, f(n) = (n-1)

• f(n) is the exponential period modulo n for numbers relatively prime with n. This means

that for any number a< n relatively prime with n, a^f(n) mod n = 1.

If you multiply a by itself f(n) times, mod n, the result is 1. If you then multiply by a one more
time you'll find the product of 1* a = a (we are back where we started).
 

a^f(n) * a = a^{f(n) + 1} mod n = a
 

We can use this knowledge to find d for c = m^e mod n so that c^d mod n = m. This lets us
encrypt and decrypt with RSA.
 

c^d mod n = (m^e)^d mod n = m^ed mod n = m^{f(n) + 1} mod n = m mod n

 
To find d we solve this equation:
 

d = e^-1 f(n) + 1
 

But since there is a risk of not finding an integer solution to this equation we compute d mod f(n):
 

d = e^-1 mod f(n)
 

As you see we are able to compute d from e and n, the question now is if this jepordize our
security? Well no it does not!
RSA uses an important property of Euler's function, it is "multiplicative".
If p and q are relative prime, then f(pq) = f(p)f(q). Hence, for primes p and q and n = pq:

f(n) = (p1)(q-1)

d = e^-1 mod(p-1)(q-1)
 
 
 
 
 

Generating the public and private key

In the RSA cryptosystem, the public -and private key work together as a pair. The public key
encrypts our data, while only the corresponding private key can decrypt it.

When generating a pair of keys we start out by selecting two large primes, p and q. Then we
compute the product of these numbers, and use it as the modulus, n.
 

n = pq
 

The next step is to choose a small odd integer (the public exponent) e, which will be a part of the
public key.

Note!
e should not have any factors in common with:
 

(p-1)(q-1)
 

When we have choosen a value for e, we will need to compute a corresponding value d, this
value will be a part of the private key. To do this we compute the multiplicative inverse of e,
mod(p-1)(q-1):
 

d = e^-1 mod (p-1)(q-1)
 

So, we got:
 

P_key = (e, n)    Public key

S_key = (d, n)    Private key
 

Note!
Remember that the two primes p and q must be kept private so that no one can compute S_key .
 
 
 
 
 

Encrypting

When encrypting one should start by selecting a blocksize that is less then n. Then to encrypt a
plaintext message we use:
 

C_i = m_i^e mod n
 

Use public (e, n) to get the numerical value of m_i , raise it to the power of e, and then take the
result mod n. => block of ciphertext C_i .

mod n ensures that C_i fits into the same size block as the plaintext.
 
 
 
 
 

Decrypting

To decrypt a plaintext message we use the following equation:
 

m_i = C^d_i mod n
 

Use private (d, n) to get the numerical value of C_i , raise it to the power of d and then take the
result mod n.
 

Difficulty of breaking RSA

As mentioned before, RSA is considered very secure!

It's very easy to multiply two prime numbers, a number that is evenly divisible by only itself and
1 (e.g. 11). However, it's extremely timeconsuming to factor large numbers ( the process of
finding the numbers that evenly divide another number).
One way to break RSA would be to factor n into its prime factors, p and q. From p, q and e
one could easily find d. The complex part is the factorization of n, this is the security of RSA.
The existence of cryptosystems like this has lead to an explosive research about factoring
algorithms. In oder to break RSA we have to depend on better factoring algorithms, since
hardware improvements don't weaken the cryptosystem (as long as the RSA users increase
their key size constantly). Hardware improvements will allow the RSA user to use much longer
keys then before without slowing down the computers performance, while we only get to factor
the number a couple of digits longer then before.

An other attack at the RSA security would be to recover an encrypted message and forge
signatures without any knowledge of the private key. This is done by computing the roots of e,
mod n. eth root of c mod n is the message, since C = m^e.
 
 
 
 
 

Key size in the RSA algorithm

The key size in RSA is the size of mod n. The primes, p and q should be of equal length, because
if one of the primes is much smaller then the other it's easyer to factor the modulus. If modulus is
1024 bits, then p and q should have a length of roughly 512 bits each.
When selecting a size for modulus one should start by determine the secrecy of the data which
are to be protected and for how long it should stand up against an attack.
The larger size of the modulus you choose , the greater security you obtain.With a key size length
of 2048 bits the protected data will be secure for a long time to come. However, long key lengths
are not suitable for file security, a key long enough for ultimate security would be to slow for routine
use in a filesystem. The larger size for modulus you choose, the slower algorithm operations you will
get. Doubling the modulus length will increase the time required for encryption by a factor of four,
and for decryption by a factor of eight.
Since the length of the private exponent increases proportionally and not remains fixed as the public
exponent, private key operations is affected more.
 
 
 

 
 
Selecting primes

Many people belive that one should use strong primes (p, q) to get mod n, since they hold some
properties that makes it harder to factor the product n.
However, the factoring methods we use today has as good chance on strong primes as it has on
weaker. Therefor one should choose large enough primes to increase security.
 
 
 
 
 

Some factoring methods

O- refers to the upper bound of the asymptotic running time of an algorithm.

There is two types of factoring algorithms, and these are: general purpose and special purpose.
Special-purpose algorithms are best for factoring numbers with small factors. If a number is
being of a special form it often has an easy way of expressing it, e.g. it might be a fermat number.
Some special-purpose algorithms are: The pollard rho method, the pollard p-1 method and the
elliptic curve method (ECM). However, these algorithms are not fast enough to factor a large
mod as in RSA.

When dealing with RSA where the modulus hold very large factors, general-purpose factoring
algorithms are the more important ones. Mod used in RSA are created to be general numbers, a
general number is one with no spec. form that might make it easier to factor.
Todays best general-purpose algorithm is the Number Field Sieve (NFS), it runs in time around
O(e1.9(lnn)1/3(lnlnn)2/3). New improvements to the NFS makes it more efficient then the
previously most widely used MPQS in factoring numbers larger then 115 digits. A variant of the
NFS has recently been used to factor RSA-155.
 

Here follows an example to implement NFS for factoring numbers around  20-digits:
================================================================
 

function SelectPolynomial(n);
    /* select a degree according to the asymptotic formula */
    d := Round( Root( 3 * Log(n)/Log(Log(n)) , 3 ) );
print "degree ", d;

    m := Iroot( n, d );
print "m := ", m, ";";

    coeffs := [];
    for i := d to 0 by -1 do
 temp2 := m^i;
 coeff := n div temp2;
 /* Append (~coeffs, coeff); */
 coeffs[i+1] := coeff;
 n -:= coeff*temp2;
    end for;

    P<X> := PolynomialRing( IntegerRing() );
    f := P!coeffs;
    return f, m, d;

end function;
 

procedure RationalSieve( ~sieve_array, y, FB, log_primes, ~prev_roots,
  m_mod_p, sieve_len);
    /*
     *  RATIONAL SIEVE
     */
    sieve_array := [0 : i in [1..sieve_len]];

    for i in [1..#FB] do
 p := FB[i];
 logp := log_primes[i];
 /*
  *  Compute  loc  - the first location in the sieve array
  *  where  p  divides the corresponding residue
  */
 loc := prev_roots[i] - m_mod_p[i];
 if loc lt 0 then
     loc +:= p;
 end if;
 prev_roots[i] := loc;
 /*  sieve begins at location 1, so skip location 0 */
 if loc eq 0 then
     loc := p;
 end if;

 /*  MAIN SIEVE LOOP  */
 while loc le sieve_len do
     sieve_array[loc] +:= logp;
     loc +:= p;
 end while;

    end for;

end procedure;
 

procedure AlgebraicSieve( ~nf_sieve_array, y, ~nf_prev_roots, log_primes,
  R_p_set, sieve_len );
    /*
     *  NUMBER FIELD SIEVE
     */
    nf_sieve_array := [0 : i in [1..sieve_len]];
    for i in [1..#R_p_set] do
 R_p := R_p_set[i];
 p := R_p[1];
 r := R_p[2];
 logp := R_p[3];

 loc := nf_prev_roots[i] - r;
 if loc lt 0 then
     loc +:= p;
 end if;
 nf_prev_roots[i] := loc;
 if loc eq 0 then
     loc := p;
 end if;

 /*  MAIN SIEVE LOOP  */
 while loc le sieve_len do
     nf_sieve_array[loc] +:= logp;
     loc +:= p;
 end while;

    end for;
end procedure;
 

procedure ScanSieveArray( J, b, bm, y, d, sieve_array, nf_sieve_array,
  error_term, ~num_rels, sieve_len, ~M, FB, prev_roots, nf_prev_roots,
  R_p_set, enough_rels, ~smooth_alg_elts, char_cols, char_offset );
 /*  scan sieve array
  */
    threshold := Round( Log( bm ) ) - error_term;
    zero := [0: i in [1..d]];
    x := zero;
    x[1] := 1; x[2] := b;
    nf_threshold := Round( Log( Abs( Norm( J!x ) ) ) ) - error_term;
    for a in [1..sieve_len] do
 if sieve_array[a] ge threshold then
     /*  rational side appears to be smooth */
     if nf_sieve_array[a] ge nf_threshold then
  /*  number field side appears to be smooth */
  if Gcd(b, a) ne 1 then
      /*  relation is redundant */
      continue;
  end if;

  /*  see if it really is smooth */
  relation := [];
  rational_side := a + bm;
  for i in [1..#FB] do
      p := FB[i];
      if a mod p eq prev_roots[i] then
   e := 0;
   quot, rem := Quotrem( rational_side, p );
   repeat
       rational_side := quot;
       e +:= 1;
       quot, rem := Quotrem( rational_side, p );
   until rem ne 0;
   Append( ~relation, [i, e] );
      end if;
  end for;
  if Abs(rational_side) ne 1 then
      /*  rational side is not smooth :-( */
      continue;
  end if;

  /*  try algebraic side */
  x := zero;
  x[1] := a; x[2] := b;
  alg_elt := J!x;
  norm := IntegerRing()!Norm(alg_elt);

  for i in [1..#R_p_set] do
      R_p := R_p_set[i];
      p := R_p[1];
      if a mod p eq nf_prev_roots[i] then
   e := 0;
   quot, rem := Quotrem( norm, p );
   repeat
       norm := quot;
       e +:= 1;
       quot, rem := Quotrem( norm, p );
   until rem ne 0;
   Append( ~relation, [i+#FB, e] );
      end if;
  end for;
  if Abs(norm) ne 1 then
      /*  algebraic side is not smooth :-( */
      continue;
  end if;

  /*  The relation is a keeper! */
print "a := ", a, "; b:= ", b,";";
  num_rels +:= 1;

  /*  Compute the character columns corresponding to
      alg_elt  */
  for i in [1..#char_cols] do
      p := char_cols[i][1];
      r := char_cols[i][2];
      if LegendreSymbol( (a + b*r) mod p, p ) eq -1 then
   M[num_rels, i + char_offset] := 1;
      end if;
  end for;

  /*  store the algebraic element */
  Append( ~smooth_alg_elts, alg_elt );

  /*  store relation in matrix */
  for j in [1..#relation] do
      M[num_rels, relation[j, 1]] := relation[j, 2];
  end for;

  if num_rels eq enough_rels then
      break;
  end if;

  /*  update the  nf_threshold  - since the norms
      grow somewhat quickly, we waste a lot of time
      on false reports if this update is not made */
  x := zero;
  x[1] := a; x[2] := b;
  nf_threshold := Round( Log( Abs( Norm( J!x ) ) ) );
  nf_threshold -:= error_term;
     end if;
 end if;
    end for;
end procedure;
 

function NFS( n )

    f, m, d := SelectPolynomial(n);
    fprime := Derivative( f );

    J<alpha> := NumberField( f );

    /*  choose  y  - the bound for smoothness  */
    dlogd := d*Log(d);
    temp := 1.0/d * Log( n );
    e := dlogd + Sqrt( dlogd^2 + 4*temp*Log(temp) );
    y := Round( Exp( 0.5*e ) );
    print "smoothness bound is ", y;

    /*  prepare data for rational sieve */
    FB := [p : p in [2..y] | IsPrime( p ) ];
    log_primes := [Round(Log(p)) : p in FB];
    prev_roots := [0: p in FB];
    m_mod_p := [m mod p: p in FB];

    /*  prepare data for the algebraic sieve */
    cols := #FB;
    R_p_set := [];
    nf_prev_roots := [];
    for p in FB do
 K := GF(p);
 roots_mod_p := Roots( f, K );
 for i in [1..#roots_mod_p] do
     r := IntegerRing()!roots_mod_p[i][1];
     /*  also include the rounded logarithm of  p  in the storage */
     Append( ~R_p_set, [p, r, Round(Log(p))] );
     Append( ~nf_prev_roots, 0 );
     cols +:= 1;
 end for;
    end for;
    smooth_alg_elts := [];

    /*  create the character columns */
    char_offset := cols;
    num_char_cols := 3 * Ilog2( n );
    char_cols := [];
    p := NextPrime( y );
    i := 0;
    repeat
 K := GF(p);
 roots_mod_p := Roots( f, K );
 for j in [1..#roots_mod_p] do
     r := IntegerRing()!roots_mod_p[j][1];
     Append( ~char_cols, [p, r] );
     i +:= 1;
     if i eq num_char_cols then
  break;
     end if;
 end for;

 p := NextPrime( p );
    until i eq num_char_cols;
    cols +:= num_char_cols;

    enough_rels := cols+50;
print "will quit after", enough_rels," relations";

    /*  allow for an error in the sieve threshold */
    error_term := 3;

    /*  set up matrix */
    M := RMatrixSpace (IntegerRing(), enough_rels, cols)!0;

    num_rels := 0;
    b := 1;
    /*  bm = b*m */
    bm := m;
    sieve_len := y * 25;

    while true do
 RationalSieve( ~sieve_array, y, FB, log_primes, ~prev_roots,
   m_mod_p, sieve_len );

 AlgebraicSieve( ~nf_sieve_array, y, ~nf_prev_roots, log_primes,
   R_p_set, sieve_len );

 ScanSieveArray( J, b, bm, y, d, sieve_array, nf_sieve_array,
   error_term, ~num_rels, sieve_len, ~M, FB, prev_roots,
   nf_prev_roots, R_p_set, enough_rels, ~smooth_alg_elts,
   char_cols, char_offset );

 bm +:= m;
 b +:= 1;
print "Number of relations: ", num_rels;

 if num_rels ge enough_rels then
     break;
 end if;
    end while;
 

print "matrix size: ",num_rels," by ", cols;
print "finding null space";

    gf2 := GF(2);
    Mprime := RMatrixSpace (gf2, num_rels, cols)!M;
    time null_space := NullSpace( Mprime );

    /*  "free" Mprime */
    Mprime := 0;

    for j in  [1..Dimension(null_space)] do
print "trying null space vector #",j;

 /*  get the first element of the solution vector */
 soln := ChangeUniverse (Eltseq (null_space.j), IntegerRing());

 /*  compute the exponents of a relation that involves an
     algebraic square and an integer square
  */

 exps := RSpace(IntegerRing(), cols)!0;
 for i in [1..num_rels] do
     if soln[i] eq 1 then
  exps +:= M[i];
     end if;
 end for;

 /*  compute the square root  x  of the integer element of the relation
  */
 x := 1;
 for i in [1..#FB] do
     e := exps[i];
     if e gt 0 then
  x := (x * ( FB[i]^(e div 2) ) ) mod n;
     end if;
 end for;
 x := ( x * Evaluate( fprime, m ) ) mod n;
print x,"^2 mod n = ", x^2 mod n;

 list := [];
 for i in [1..num_rels] do
     if soln[i] eq 1 then
  Append( ~list, smooth_alg_elts[i] );
     end if;
 end for;
 Append( ~list, Evaluate( fprime, alpha )^2 );

 /*  Compute the square root  beta  of the algebraic element */
 ok, l := Root(2, list, []);
        if ok eq false then
            print "Element is not a square... continuing!";
            continue;
        end if;

 /*  map the sqrt to an integer  v  modulo  n  */
 v := 1;
 for i in [1..#l] do
     list := l[i];
     prod_list := 1;
     for j in [1..#list] do
  seq := Eltseq( list[j] );
  elt := 0;
  for k in [0..d-1] do
      num := Numerator( seq[k+1] ) mod n;
      den := Denominator( seq[k+1] ) mod n;
      elt +:= ( ( num * Modinv( den, n ) mod n) *
        Modexp( m, k, n ) ) mod n;
  end for;
  prod_list := (prod_list * elt) mod n;
     end for;
     v := v * Modexp( Modinv( prod_list, n ), 2^(i-1), n ) mod n;
 end for;
 
print v,"^2 mod n = ", v^2 mod n;

 gcd := Gcd(x-v, n);
print "Gcd of ",x-v," and ",v," is ", gcd;
 if gcd ne 1 and gcd ne n then
     print "FACTOR: ", gcd;
     return gcd;
 end if;
    end for;

print "no factor found :-( ";
    return 0;

end function;


================================================================