PseudoRandom.html

Pseudo random strings

ŠMike May, S.J., 2002, maymk@slu.edu

>

Preliminaries

The book talks of using a pseudo random string as a means of encryption. To be able to to use this technique we first need some preliminaries. In particular we need procedures for XOR on a pair of bits. That procedure is used to XOR bytes. The procedure parses or reads a 0 or 1 string as a number, add mod 2, then convert back to a string.

> bitXOR := (bit1,bit2) -> convert(((parse(bit1)+parse(bit2)) mod 2),string):
byteXOR := (byte1,byte2) ->
cat(seq(bitXOR(substring(byte1,i), substring(byte2,i)), i=1..8)):

> byteXOR("01001101", "01100110");

We also want a number of procedures to convert between data types. The messages will start out as ASCII characters. To use an XOR procedure we will want each character to be represented as a byte string composed of eight bits, with leading zeroes printed. To store ciphertext we will want to use two character hex strings. Thus we need procedures to go from character to binary string to hex string.

>    charToBinByte := proc(character)
   local binChar:
   binChar := convert(op(convert(character, bytes))+256,binary):
   substring(convert(binChar,string),2..9):
end:

> binToHexByte := binString ->
substring(convert(convert(parse(binString),decimal,binary)+256,hex),2..3):

> s1 := charToBinByte("\n");

> h1 := binToHexByte(s1);

We also want procedures to convert back.

>    hexToBinByte := hexString ->
   substring(convert(convert(convert(hexString, decimal,hex)+256,binary),
       string),2..9):

> binByteToChar := binString ->
convert([convert(binString,decimal,binary)],bytes):

> s2 := hexToBinByte(h1);

> binByteToChar(s2);

We also need routines from the conversion worksheet that can arrange the hex strings into words and break the words back into pieces.

> blocker := proc(hexvec,bsize)
local numCharacters, paddingNum, numWords, i, j, temp, hexblock;
temp := hexvec;
numCharacters :=linalg[vectdim](hexvec);
numWords := ceil(numCharacters/bsize);
paddingNum := numWords*bsize - numCharacters;
temp := [op(temp),seq("00",j = 1..paddingNum)];
hexblock := array(1..numWords,
[seq( cat(seq(temp[bsize*i + j], j = 1..bsize)), i=0..numWords-1)]):
convert(hexblock,list):
end:

>    unblocker := (hexblock,bsize) ->
   map(hexString -> seq(substring(hexString,2*j-1..2*j), j = 1..bsize),
      hexblock):

Setting up Blum-Blum-Shub

To set up the Blum-Blum-Shub method of producing a pseudorandom string, we first need to produce a pair of primes. We want primes congruent to 3 mod 4. Since we want to harvest 4 bits at each step we would like the primes to be about 1000.

> p := nextprime(rand(1000..10000)());
while ((p mod 4) = 1) do p := nextprime(p) od;
q := nextprime(rand(1000..10000)());
while ((q mod 4) = 1) do q := nextprime(q) od;
n := p*q;

To make this more predictable we can fix p and q.

> p := 5323;
q := 7411;
n := p*q;

Next we need a seed. The seed should be relatively prime to n.

> x0:= rand(n)();
while (igcd(x0,n)>1) do x:= rand(n)() od;

Once again, we then fix the seed so that we can get the same result on repeated runnings of the worksheet.

> x0 := 8288583;

Now we produce a procedure that takes a key, runs two rounds of the procedure to produce a key byte and a new seed to use in the next round..

>    nextKeyByte := proc(modulus, key)
   local stream, x1, x2:
   x1 := Power(key,2) mod modulus:
   stream := convert(x1 mod 16, hex):
   x2 := Power(x1, 2) mod modulus:
   stream := cat(stream, convert(x2 mod 16, hex)):
   [x2, hexToBinByte(stream)];
end:

> oneStep := nextKeyByte(n,x0);

> oneStep := nextKeyByte(n,oneStep[1]);

This lets us produce a string of bytes to use as a key.

> x1 := x0:
for i from 1 to 20 do
nextStep := nextKeyByte(n,x1):
x1 := nextStep[1]:
print(i, nextStep[2]);
od:

>

Encryption and Decryption with BBS

We are ready to use this to encode a message. First we create a message to encode:

> mess1 := "AZaz Good morning Mr. Phelps. Your job today, should you choose
to accept it, is to learn to use Blum-Blum-Shub encryption. AZaz";

> messlength := length(mess1);

We encrypt the message and write the code as words of 8 hex characters corresponding to 4 ASCII characters.

>    x1 := x0:
cipher1 := []:
for i from 1 to messlength do
  oneStep := nextKeyByte(n,x1):
  oneByte := byteXOR(oneStep[2], charToBinByte(substring(mess1,i))):
  hexByte := binToHexByte(oneByte):
  x1 := oneStep[1]:
  cipher1 := [op(cipher1), hexByte]:
od:
cipher1;

> code := blocker(cipher1,4);

To decrypt we reverse the process.

> cipher2 := unblocker(code,4);

>    x1 := x0:
decipher1 := []:
for i from 1 to messlength do
  oneStep := nextKeyByte(n,x1):
  oneByte := byteXOR(oneStep[2], hexToBinByte(cipher2[i])):
  oneChar := binByteToChar(oneByte):
  x1 := oneStep[1]:
  decipher1 := [op(decipher1), oneChar]:
od:
decipher1;

> cat(op(decipher1));

Since we would like to be able to do this with arbitrary messages, we produce procedures for encryption and decryption. The encryption procedure should take a message, a modulus (the n value), an initial key (the x0 value) and the number of ASCII characters in a code word.

>    BBSEncrypter := proc(message, modulus, key1, blocksize)
   local messlength, x1, cipher1, oneStep, oneByte, hexByte, i:
   messlength := length(message);
   x1 := key1:
   cipher1 := []:
   for i from 1 to messlength do
      oneStep := nextKeyByte(modulus,x1):
      oneByte := byteXOR(oneStep[2], charToBinByte(substring(message,i))):
      hexByte := binToHexByte(oneByte):
      x1 := oneStep[1]:
      cipher1 := [op(cipher1), hexByte]:
   od:
   blocker(cipher1,blocksize);
end:

> cipherText := BBSEncrypter(mess1,n,x0,4);

The decryption routine needs the same set of information with the plaintext replaced by ciphertext.

>    BBSDecrypter := proc(codeText, modulus, key1, blocksize)
   local cipher2, messlength, x1, oneStep, oneByte, oneChar, decipher1, i;
   cipher2 := unblocker(codeText,blocksize):
   messlength := nops(cipher2):
   x1 := key1:
   decipher1 := []:
   for i from 1 to messlength do
      oneStep := nextKeyByte(modulus,x1):
      oneByte := byteXOR(oneStep[2], hexToBinByte(cipher2[i])):
      oneChar := binByteToChar(oneByte):
      x1 := oneStep[1]:
      decipher1 := [op(decipher1), oneChar]:
   od:
   decipher1;
   cat(op(decipher1));
end:

> BBSDecrypter(cipherText,n,x0,4);

Note that the extra characters correspond to filling out the last code word with spaces. This is one reason to have an end of message string.

Exercise:

1) Use BBS to encrypt a message and post it to the bulletin board. You need to post the encrypted message, the modulus, and the initial key. Respond to someone else's message.

>

Using Linear Feedback Shift Registers

To set up a linear feedback shift register we start with the polynomial that corresponds to a recurrence relation defining the linear feedback.

> p1 := x^8 + x^4 +x^3 + x^2 + 1:

We can turn it into a matrix that works on a block of bits, shifting then up one place and using the linear feedback for the last bit. To do that we want the transpose of the companion matrix.

> m1 := linalg[transpose](linalg[companion](p1,x));

If we now take the nth power of the matrix we have one that replaces a byte of bits with the next byte.

> shiftMat := map(modp, evalm(m1^8),2);

If we start with 8 bits of the key string, we get the next 8 bits by multiplying by the matrix mod 2.

> keyVect := vector([1,1,0,1,0,1,1,0]);
v2 := map(modp, evalm(shiftMat&*keyVect),2);

We want a procedure to do this automatically.

> shiftWord := (mat, vect) -> map(modp, evalm(mat&*vect),2);

This lets us produce a bit string that would continue for 255*8 bits without repeating.

> v2 := keyVect;
for i from 1 to 10 do
v2 := shiftWord(shiftMat, v2);
od;

We also want procedures to convert between a vector of bits and the string formed by concatenating the elements of the vector.

>    binByteToVector := binByte ->
    vector([seq(parse(substring(binByte,i)), i=1..8)]);
vectorToBinByte := vect ->
    cat(seq(convert(v1[i],string), i=1..8));

We are ready to use this stream to encrypt a message. Let's repeat the message from above.

> mess1;
messlength := length(mess1);

>    v1:= keyVect:
cipher1 := []:
for i from 1 to messlength do
  oneStep := vectorToBinByte(v1):
  oneByte := byteXOR(oneStep, charToBinByte(substring(mess1,i))):
  hexByte := binToHexByte(oneByte):
  v1 := shiftWord(shiftMat,v1):
  cipher1 := [op(cipher1), hexByte]:
od:
cipher1;
code := blocker(cipher1,4);

Decryption reverses the process with the same key

>    cipher2 := unblocker(code,4);
v1 := keyVect:
decipher1 := []:
for i from 1 to messlength do
  oneStep := vectorToBinByte(v1):
  oneByte := byteXOR(oneStep, hexToBinByte(cipher2[i])):
  oneChar := binByteToChar(oneByte):
  v1 := shiftWord(shiftMat,v1):
  decipher1 := [op(decipher1), oneChar]:
od:
decipher1:
cat(op(decipher1));

Exercise:

2) Use LFSR to encrypt a message and post it to the bulletin board. You need to post the encrypted message, the polynomial, and the initial key. Respond to someone else's message.

>