RSA

Stephan Kaufmann

Reference

Author

Stephan Kaufmann
Institute of Mechanics
Swiss Federal Institute of Technology
ETH Zentrum, HG F38.4 
CH-8092 Zuerich
Switzerland
kaufmann@ifm.ethz.ch

Copyright Notice

Copyright © 1992 by Stephan Kaufmann

Permission is hereby granted to make copies of	this file for any purpose other than direct profit,	or as part of a commercial product, provided this copyright notice is left intact.	Sale is prohibited.
	
Permission is hereby granted to reproduce part or all of this file provided that the source is acknowledged.

Version

Notebook Version 2.1 (E)

Requirements

Mathematica Version: 2.0 or higher.

If[$VersionNumber < 2.0, Print[
  "This package requires Mathematica version 2.0 or higher."]]

Discussion

Algebraic Tools

The RSA system is based on Euler's theorem:

If a and m are relatively prime cardinals, then a^(φ(m)) ≡ 1 (mod m).

φ(m) is Euler's totient function (i.e. the number of cardinals k with 0 < k ≤ m which are relatively prime to m).

For a prime p, we have: φ(p) = p-1;
for two primes p and q: φ(p q) = (p-1)(q-1).

RSA Encryption

The receiver of a message generates two (large) primes p and q and a number e, which is relatively prime to φ(p q) = (p-1)(q-1). He calculates the product n = p q and the (multiplicative) inverse d of e modulo φ(n): d e ≡ 1 (mod φ(n)).

The receiver puts n and e into a public directory; he keeps p, q and d secret.

The sender of a message uses the numbers n and e of the receiver. He transforms the message according to a public scheme into a cardinal m < n or a sequence of such numbers. Then, he calculates the encoded message c(m) according to c(m) = m^e (mod n). This number (or the sequence of such numbers) is transmitted.

The receiver reconstructs the message with the calculation
c(m)^d = m^(e d) = m^(1+k φ(n)) ≡ m (mod n).

The safety of the encryption is based on the fact that there are no known polynomial-time algorithms for factoring numbers. If p and q are large enough, their product n can not be factored within reasonable time (or, equivalently, φ(n) calculated).

Further Restrictions for the Primes

For the encryption to be save, the numbers p and q must be chosen large enough (one hundred or more digits). Furthermore, p–1 (and q–1) should have a large prime factor. The number e must also be chosen large.

Literature

Akritas, A. G.: Elements of Computer Algebra with Applications. Wiley, New York, 1989.

Rivest, R. L., A. Shamir and L. Adleman: A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM 21, 120-126, 1978.

The Functions in this Package

RSAPrime[digits] generates prime suitable for RSA with digits digits.

GenerateE[p, q] generates a suitable number e for two primes p and q.

GenerateD[e, p, q] calculates the number d for a given e (and p and q).

StringToList[text, n] transforms strings into a list of cardinals < n.

ListToString[l] transforms a list of cardinals (from StringToList) back into the original string.

RSAEncodeNumber[num, e, n] encodes a cardinal num with e and n.

RSADecodeNumber[num, d, n] decodes a number num with d and n.

RSAEncode[text, e, n] encodes a string.

RSADecode[l, d, n] decodes a list of cardinals.

Example

The generation of large suitable primes takes some time. It is a good idea to do this in the background. We demonstrate the functions with an unrealistically small example.

Generation of the Primes p and q

p = RSAPrime[6]

q = RSAPrime[6]

Calculation of n, e, d

n = p q

e = GenerateE[p, q]

d = GenerateD[e, p, q]

Encryption and Decryption of Cardinals

c = RSAEncodeNumber[123, e, n]

RSADecodeNumber[c, d, n]

Encoding and Decoding of Strings by Lists of Numbers

StringToList["This is a message", n]

ListToString[%]

Encryption and Decryption of Text

c = RSAEncode["A secret message", e, n]

RSADecode[c, d, n]

Using Larger Primes

The following primes have been generated with RSAPrime.

p =
332715112660848742187755808851902864945816936127916014252\
  3661652581105578513717982486654235124785151

q =
120791468413759348683463308420511774373133760151037399776\
  0717454678735342949711476106521763447795837

The example is more realistic now.

n = p q

e = GenerateE[p, q]

d = GenerateD[e, p, q]

c = RSAEncode["A secret message", e, n]

RSADecode[c, d, n]

Implementation

Preparation

BeginPackage["SKPackages`RSA`"];

RSAPrime::usage =
"RSAPrime[digits] returns a prime suitable for RSA with the given number of digits.";

GenerateE::usage =
"GenerateE[p, q] generates a random encoding exponent e which is relatively prime to (p-1)(q-1).";

GenerateD::usage =
"GenerateD[e, p, q] returns the multiplicative inverse of e mod((p-1)(q-1)).";

StringToList::usage =
"StringToList[text, n] converts a given string to block of numbers smaller than n.";

ListToString::usage =
"ListToString[l] converts a list of numbers (resulting from StringToList) to the original text string.";

RSAEncodeNumber::usage =
"RSAEncodeNumber[num, e, n] encodes the given number num using RSA with exponent e and modulus n.";

RSADecodeNumber::usage =
"RSADecodeNumber[num, d, n] decodes the given number num using RSA with exponent d and modulus n.";

RSAEncode::usage =
"RSAEncode[text, e, n] encodes the given text by converting it to a list of numbers and using RSA with exponent e and modulus n.";

RSADecode::usage =
"RSADecode[l, d, n] decodes the given list of numbers l by using RSA with exponent d and modulus n and converting the result back to the original text string.";

Begin["`Private`"];

Good Primes for RSA

GoodRSAPrimeQ[n_Integer, l_Integer] :=
  PrimeQ[n] &&
  Module[{d = 1, m = (n-1)/2},
    While[d <= l && !PrimeQ[m/d], d++];
    d <= l
  ]

RSAPrime[digits_Integer] :=
  Module[{l, cand},
    cand = Random[Integer, {10^(digits-1), 10^digits-1}];
    l = 10^Floor[Log[10., cand]/30];
    If[EvenQ[cand], cand++];
    While[!GoodRSAPrimeQ[cand, l], cand += 2];
    cand
  ]

RSA with Numbers

GenerateE[p_Integer, q_Integer] :=
  Module[{res, n = p q, phi = (p-1)(q-1)},
    res = Random[Integer, {p, n}];
    While[GCD[res, phi] != 1,
      res = Random[Integer, {p, n}]];
    res
  ]

GenerateD[e_Integer, p_Integer, q_Integer] :=
  PowerMod[e, -1, (p-1)(q-1)]

RSAEncodeNumber[num_Integer, e_Integer, n_Integer] :=
  PowerMod[num, e, n] /; num < n

RSADecodeNumber[num_Integer, d_Integer, n_Integer] :=
  PowerMod[num, d, n]

Conversion of Text

ConvertString[str_String] :=
  Fold[Plus[256 #1, #2]&, 0, ToCharacterCode[str]]

StringToList[text_String, n_Integer] :=
  Module[
    { 
      blockLength = Floor[N[Log[256, n]]],
      strLength = StringLength[text]
    },    
    ConvertString /@ Table[StringTake[text, 
        {i, Min[strLength, i + blockLength - 1]}],
      {i, 1, strLength, blockLength}]
  ] /; n > 256

MakeList[0] = {};

MakeList[num_Integer] :=
  Append[MakeList[Quotient[num, 256]], Mod[num, 256]]

ConvertNumber[num_Integer] := FromCharacterCode /@ MakeList[num]

ListToString[l_List] :=
  StringJoin[ConvertNumber /@ l]

RSA with Text

RSAEncode[text_String, e_Integer, n_Integer] :=
  RSAEncodeNumber[#, e, n]& /@
    StringToList[text, n] /; n > 256

RSADecode[l_List, d_Integer, n_Integer] :=
  ListToString[RSADecodeNumber[#, d, n]& /@ l]

Finish

End[ ];

EndPackage[ ];