Assignment 02 Questions
Q: (Again) How do I read files into Magma? More specifically,
how can I read in a file and get the 0's and 1's as a sequence
of integers?
Use Read and Split to extract a sequence of strings, then once
you identify the entries corresponding to a binary string, you can
use StringToInteger to convert the "0"'s and "1"'s to integers:
S := Split(Read("filename"));
bits := [ StringToInteger(S[3][i]) : i in [1..#S[3]] ];
You might need to further convert them to elements of Z/2Z, in
which case you'd do something like this:
FF := FiniteField(2);
bits := [ FF | StringToInteger(S[3][i]) : i in [1..#S[3]] ];
Q: Any hints for the LFSR question?
Sure. Suppose C1 and C2 are your binary ciphertext sequences.
Then the sum
KeySum := [ C1[i] + C2[i] : i in [1..Min(#C1,#C2)] ];
should be the bit sequence of a power series (f1*g2+f2*g1)/(g1*g2).
The Berlekamp-Massey algorithm is designed to return the denominator
polynomial g1*g2:
g1g2 := BerlekampMassey(KeySum);
After factoring, you just have to decide which of the two factors
is the connection polynomial of each of the ciphertexts.
Alternatively you could let M be the binary sequence of the given
initial message segment:
M := BitEncoding("To: James S. Bond <007@hmss.gov.uk>");
KeyStream1 := [ C1[i]+M[i] : i in [1..#M] ];
KeyStream2 := [ C2[i]+M[i] : i in [1..#M] ];
Then Berlekamp-Massey should give you the individual connection
polynomials.
Q: Any hints for the ElGamal question?
Follow the suggestion from class (see also week 12 tutorial) to
reduce the problem to a baby-step, giant-step for each of the
prime power divisors of p-1. Make sure that you use indexed sets
for the baby steps:
// Set up prm_pows to be the prime power divisors q_i of p-1,
// where (p,a,c) be the ElGamal public key, and find each of
// the exponents x_i mod q_i.
mod_exps := [ ];
prm_pows := [ fac[1]^fac[2] : fac in Factorization(p-1) ];
for qi in prm_pows do
ai := a^((p-1) div qi);
ci := c^((p-1) div qi);
mi := Ceiling(Sqrt(qi-1));
BabySteps := {@ ai^k : k in [0..mi-1] @};
aim := ai*BabySteps[mi]; // giant step size
bi := ci; // initial point
for ji in [0..mi] do
ki := Index(BabySteps,bi)-1;
if ki ge 0 then
xi := (ki-ji*mi) mod qi;
Append(~mod_exps,xi);
break ji; // done, so exit the loop over ji
end if;
bi *:= aim; // take another giant step
end for;
end for;
x := CRT(mod_exps,prm_pows);
Note that a and c should be defined as elements of the finite field
FiniteField(p). Otherwise, you can work with their integer
representatives, but should write 'ai := Modexp(a,(p-1) div qi,p);'
rather than 'ai := a^((p-1) div qi);', etc.
Q: How do I determine if a large integer is a cube? Don't I need
a large amount of precision?
Rather than using a real cube root (i.e. as a real number), you can
test whether an integer, say m3, is an exact cube with IsPower(m3,3).
Q: What #%?@#$! encoding is used for the RSA ciphertext? Why can't
I just use StringToInteger(CT,2)?
The decoding of bits strings to integers is given by the following
function:
function BitStringToInteger(S)
return &+[ bits[i+1]*2^i : i in [0..#S-1] ]
where bits := [ StringToInteger(S[i]) : i in [1..#S] ];
end function;
Note that this equivalent to reversing the string CT -> RevCT,
then applying StringToInteger(RevCT,2). I realise this causes
some confusion, so just use the above function.
Q: How should I go back from an integer to a bit sequence or to
a bit string?
You probably want to specify the length t of the bit stream, since
for decoding purposes, it must be a multiple of 8. The following
lines convert an integer to a bit sequence.
function IntegerToBits(n,t)
bits := [ FiniteField(2) | ];
for i in [1..t] do
b := n mod 2;
n := n div 2;
Append(~bits,b);
end for;
return bits;
end function;
To create the same bit sequence as a string, you can do:
function IntegerToBitString(n,t)
bitstg := "";
for i in [1..t] do
b := n mod 2;
n := n div 2;
bitstg *:= IntegerToString(b);
end for;
return bitstg;
end function;
Note that, when t is the minimal integer greater than log_2(n),
this is the reverse of the binary encoding IntegerToString(n,2),
but this is the preferred encoding to use for this course.
Q: Why does BitDecoding(CipherBits) get truncated? I can't encode
my ciphertext bits as LFSR ciphertext in order to decipher it.
You can encode either bits or strings in the LFSR:
> Decoding(Encoding(LFSR,[GF(2)|0,1,0,0,0,0,0,1]));
A
> Decoding(Encoding(LFSR,"A"));
A
If you try BitDecoding on ciphertext bits, which are basically random
bit strings, you will eventually hit a string of eight 0's. This is
interpretted as an EOF character, which signals Magma to abort the
string. Basically this 1 out of 256 characters is not accepted by
Magma as a string, so general binary strings fail to decode.
Since Magma can't represent the underlying ASCII string, you must use
the former encoding mechanism, which is more direct anyway (this is the
internal representation that I use for these cryptographic texts).
Q: How do I encode the plaintext for Q5?
You can either use the RSACryptosystem to do the encoding -- recall
Encoding(RSA,plaintext) where RSA is a cryptosystem -- or you can
manually encode the plaintext as integers of the required length
(and apply RSA).