Assignment 2 Questions

################################################################################
################################################################################

Q1: How do I read files into SAGE?  More specifically, how can I read in a file 
and get the 0's and 1's as bits or find the integer to which it corresponds?

B = BinaryStrings()
ct = open("Ciphertext/LastFirstMiddle.txt").read().split("\n")
# Question 1:
ct[0] == 'Q1:'
ct[1] == First LFSR ciphertext:'
ct_stream1 = B(ct[2]) # create the binary string for first LFSR sequence
ct[3] == 'Second LFSR ciphertext:'
ct_stream2 = B(ct[4]) # create the binary string for second LFSR sequence

def binary_string_to_bits(binary_string):
    FF = FiniteField(2)
    return [ FF(i) for i in binary_string._element_list ]

def bits_to_binary_string(bits):
    ZZ = IntegerRing()
    return BinaryStrings()([ ZZ(i) for i in bits ])

ct_bits1 = binary_bits(ct_stream1)
ct_bits2 = binary_bits(ct_stream2)

Suppose ct_bits1 and ct_bits2 are your binary ciphertext sequences. Then 
the bits represent the coefficients sequence of:

             m(x) + f1(x)/g1(x) and m(x) + f2(x)/g2(x)

where m(x) is the power series representing the message stream.

Then the sum

N = min(len(ct_bits1),len(ct_bits2))
ct_bit_sum = [ ct_bits1[i] + ct_bits2[i] for i in range(N) ]

should be the bit sequence of a power series (f1*g2+f2*g1)/(g1*g2).  Why?

The Berlekamp-Massey algorithm (belekamp_massey) is designed to returns 
the denominator polynomial g1*g2:

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(x) be the binary sequence of the given initial 
message segment:

m = B.encoding("To: James S. Bond <007@hmss.gov.uk>")

How would you then use this?  How many bits of information does this give 
you?

Q2: How do I read in the data for question 2?

B = BinaryStrings()
ct = open("Ciphertext/LastFirstMiddle.txt").read().split("\n")
# Question 2:
ct[5] == 'Q2:'
ct[6] == 'Weak key El Gamal ciphertext:'
ct[7] == 'Public key prime:'
p = eval(ct[8]) # evaluate the string to get the ElGamal prime p
ct[9] == 'Public key component 1:'
a = eval(ct[10]) # evaluate the string to get the ElGamal group generator a
ct[11] == 'Public key component 2:'
c = eval(ct[12]) # evaluate the string to get the ElGamal group generator c = a^k
ct[13] == 'Ciphertext component 1:'
r = eval(ct[14]) # evaluate the string to get the ElGamal ciphertext element r
ct[15] == 'Ciphertext component 2:'
s = eval(ct[16]) # evaluate the string to get the ElGamal ciphertext element s

You will have to reduce the problem to a baby-step, giant-step for each of the 
prime power divisors of p-1, as follows.  

It is very important that you create the elements a and c as finite field 
elements not the integers produced above!  This is done as follows:

FF = FiniteField(p)
a = FF(a) 
c = FF(c) 

Then and only then you can do:

prm_pows = [ fac[0]^fac[1] for fac in (p-1).factor() ]

mod_exps = [ ]

for qi in prm_pows:
    ai = a^((p-1).div(qi))
    ci = c^((p-1).div(qi))
    mi = RR(qi).sqrt().ceiling()
    aik = FF(1)
    BabySteps = { }
    for k in range(mi):
        BabySteps[aik] = k; aik *= ai
    bi = ci # initial point
    for ji in range(mi):
        if BabySteps.has_key(bi):
            ki = BabySteps[bi]
            xi = (ki-ji*mi).mod(qi)
            mod_exps.append(xi)
            break # no need to continue loop
        bi *= aik

Explain how this works.

Now use the Chinese remainder theorem algorithm 'crt' to reconstruct the exponent.

Q3: How do I read in the data?

B = BinaryStrings()
ct = open("Ciphertext/LastFirstMiddle.txt").read().split("\n")
# Question 3:
ct[17] == 'Q3:'
ct[18] == 'RSA ciphertext:'
ct[19] == 'Public exponent:'
e == eval(ct[20]); # e = 3
ct[21] == 'Public modulus:'
n = eval(ct[22])
ct[23] == 'Ciphertext:'
s = B(ct[24])

Q3: How do I determine if a number is a cube?

This function gives a dirty way to do so directly in SAGE:

def is_power(x, n):
    (m, s) = pari(x).ispower()
    m = ZZ(eval(str(m)))
    s = ZZ(eval(str(s)))
    if m == n:
        return True, s
    elif m.mod(n) == 0:
        k = m.div(n)
        s = s^k
        return True, s
    return False, 0

Then just do is_power(x, 3).

Q: What #%?@#$! encoding is used for the RSA ciphertext?

The decoding of binary strings to an integer is given by the following
function:

def binary_string_to_integer(binary_string):
    c = binary_string._element_list
    return sum([ c[i]*2^i for i in range(len(c)) ]) 

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: Do the RSA and ElGamal plaintexts encode any information?

Possibly.

def integer_to_binary_string(n):
    bits = [ ]
    while n > 0:
       n, r = n.quo_rem(2)
       bits.append(r)
    return BinaryStrings()(bits)

You may have to padd the string to be of length = 0 mod 8 in order to 
get ASCII characters.