228.sagews

p=2^28+3
d=p-1
G=IntegerModRing(p)
Z=IntegerModRing(d)
g=G(3)

# 10.1 Setting up the message
B = BinaryStrings()
b = B.encoding('Kons')
b

01001011011011110110111001110011

# converting b to decimal and mapping it to an element of G
m = Z(4943726)
print m

4943726

# 10.2 (i) key generation ...
# secret key
a=Z(100)
y=g^a
# secret session key
k=Z(787)
x=Z(g^k)

# ... and signing the message
b=(m-a*x)/k
b

153551434

# the signature consists of (x,b)
x ,b

(10296631, 153551434)

# 10.2 (ii) The public key consists of
g, y

(3, 45193911)

# the verification is the comparison
g^m == y^x * G(x)^b

True

# 10.3 (i)
# the public version y of the secret key a is known
print y

45193911

M = list()
for counter in srange(3):
    i = G.random_element()
    j = G.random_element()
    while gcd(j,d) != 1:
        j = G.random_element()
    x = g^i * y^j
    b = -x*j^(-1)
    m = -x*i*j^(-1)
    M.append(m)
    print m, x, b
print M

49611642 260078794 95791111 133143918 250993899 28362908 234289665 139526448 60777607 [49611642, 133143918, 234289665]

# 10.3 (ii)
# converting to binary
for i in srange(3):
     M[i] = Integer(M[i]).binary()
# printing the corresponding ASCII
for i in srange(3):
    print B(M[i]).decoding()

@

# 10.4 (i)
m = Z(500)
x = Z(10296631)
b = Z(248708422)
k = Z(787)

# With this information, we can solve
# b=(m-a*x)/k
# for the secret key a
a = (b*k-m)/(-x)
print a

100

# 10.4 (ii)
m = [Z(501), Z(502)]
x = Z(32067479)
b = [Z(51030675), Z(60076072)]

# Solve the two equations
# b[0]=(m[0]-a*x)/k
# b[1]=(m[1]-a*x)/k
# for the common a, while eliminating the unknown k.
# One quick possibility to do this is by dividing the left resp. right sides by each other.

# The result of the algebraic manipulations is the following formula:
a = (b[0]*m[1]-m[0]*b[1])/(b[0]*x-b[1]*x)
print a

102