Question 1.
a)
p = 196065871
q = 102305491
n = p * q = 20058615200997661
φ(n)=(p−1)⋅(q−1) = 20058614902626300
find the smaller e > 1, such that gcd(e,φ(n))=1, e = 19.
Now find d such that e⋅d ≡ 1 mod φ(n) , using the Extended Euclidean algorithm, d = 13724315459691679
So the smallest public key is [n, e] = [20058615200997661, 19] The corresponding private key is d = 13724315459691679.
The code for this question is in Appendix.
b)
Bob can choose a message m, blind the message, send the blinded message to Alice to let Alice sign the message with his private key, then Alice send the signed bind message to Bob, finally Bob un- blind this message.
The code for this question is in Appendix. The steps are as follows.
i. selection of two random primes, each of length at least 100 digits.
p: 140833594693385115726324477187474934050403623182058605 002977360616302224310529980572507479005779402123174130 63
q: 105137332348468497368736378298386351043097146888966311 274386921621318577780441582731640938389370834213800419 97
ii. the public key e be smallest valid public key.
n=p*q = 148068684511079402378185544670910028396429695657590390935242421034422471 481084191890163030094123629499752941095042782115712555821328518268547699 617479197158668660448059195876291281822260258035910071417381842181336406 811
φ(n)=(p−1)⋅(q−1) = 1480686845110794023781855446709100283964296956575903909352424210 3442247148108419189016303009412362949975294107044568941152719451 1822432719961571108129120151566168820322767652529201613163101705 495229677866818547638951752
find the smaller e > 1, such that gcd(e,φ(n))=1, e = 5.
iii. Determine the private key d.
Now find d such that e⋅d ≡ 1 mod φ(n) , using the Extended Euclidean algorithm,
d= 5922747380443176095127421786836401135857187826303615637409696841376898 8592433676756065212037649451799901176428178275764610877804728973087984 6284432516480606264675281291070610116806452652406821980918711467274190 55580701
iv. A random message m of length at least 100 digits.
m= 527654088646108540362982390044019863852553381756839064739589507767331089 783254199732302674718497125124586822562788766953
v. A blinded message mb.
take a random blind number k = 13 compute the blinded message as
mb = m * pow(k, e) mod n = 195914269535679578276992820546614267309406102772642046
864356407107455662318893801581205857004254953078883215 109805529648280229
vi. Signature of m through blinded process. signed_mb = mb
unblind the signed blinded message unblind = signed_mb
vii. Direct signature of m using the private key.
m
The vi and vii
are identical. c)
It is not a secure method. Under this method each alphabet maps to a number and same alphabet maps to the same number in the encrypted message. Because in normal English text, different letter or combination have different frequency, we can use frequency analysis to attack against this method.
signs the blinded message with private key
d mod n =
829839058686429697431507501774982917502649338724644431162
214813380247614105689833967054825815182180706195384820777
566548651620733578115029532893194592922152210537678776694
48068130342605503033607921774411775774555719421
/ k mod n =
638337737451099790825032306611127652517088201370785633321 605884630932412717140017593584242409360654260945928276935
747807013459396776428911873336102664901967519402175847102
7892274540880359951229515095583474345465348096
d mod n =
638337737451099767255005770596140705771268722095880331663
242164138652010850530641513119096780909369773996449862136
589652808939025829319253486840918917632424777336675982072
6774471564815807925662147828800905828811978417
The countermeasure is to encrypt the message as whole or divide into much larger chunk to
encrypt.
Question 2. a)
First compute K:
. K = (C1)XA mod q
Because
. (C1)X= ak XA
= (aXA)k
= yAk
= K
(mod q) Then compute the M:
. M = K XOR C2
(XOR is is binary exclusive or function) From the property of XOR operation, that is if c = a XOR b, then b = a XOR c.
b)
. Because C1 =ak mod q is known and yA = axA mod q
is also
. known, if CDH
problem is not hard, then from C1 and yA, we can compute
. K=yAkmodq
=akXAmodq.
. Thus the security of the encryption function is based on CDH problem.
.
.
.
Question 3.
a)
one-way property : Ease to compute the output using the hash function given the input, but very hard to get the hash function’s input given the output.
second image resistance : given one input, it is hard to find another input to let their output same under this hash function.
collision resistance
: It is hard to find a pair of different input who have the same output under the hash function.
b)
It doesn’t satisfy any of the three key requirements.
It doesn’t satisfy one-way property. Because it is easy to find a message that have given hash value H. For example M = {0, 0, …H} has hash value H.
It doesn’t satisfy second image resistance. Because given one message, we can swap one pair of integers to get another message which has the same hash value.
It doesn’t satisfy collision resistance. Because two messages that have same with elements but with different order still have the same hash value.
c.
It doesn’t satisfy any of the three key requirements either.
It doesn’t satisfy one-way property. Because if the given hash value H is a square of an integer a. For example M = {0, 0, …a} has hash value H.
It doesn’t satisfy second image resistance. Because given one message, we can swap one pair of integers to get another message which has the same hash value.
It doesn’t satisfy collision resistance. Because two messages that have same with elements but with different order still have the same hash value.
Question 4. a.
The main difference is that message authentication code use symmetric keys and digital signatures use asymmetric keys.
The message authentication code and digital signature both fulfill the goals of Integrity and Authentication, but MAC doesn’t have non-repudiation, whereas digital signature does. Because under MAC, the receiver can falsify the message.
b.
Because Diffie-Hellman doesn’t provide authentication for the message exchanged. So third party can establish two key exchanges with both sides, intercepte the messages exchanged.
Message Authentication Codes
Yes. We can add message authentication codes to the messages exchanged, thus both
sides can verify the authentication of the message.
Public Key Digital Signatures.
Yes. The two sides can add the digital signature with their private key, and the other side
can use the opposite side’s public key to verify the message’s authentication.
Hash functions.
No. Hash functions only support integrity, it doesn’t support authentication.
Question 5.
(a)
The consequence is that others can recover the secret key. Because through the two messages and their signatures plus the information that they use the same k, we can compute the k and then compute the private key.
(b)
We can modify as follows.
The computation of S2 changes to:
. S2
=
K m
- XA S1
mod(q – 1)
When verifying the signature, change to:
. V1 = S1m
mod q
. V2 =
YAS1 a S2
mod q
. ThesignatureisvalidifV1=V2.
Thereasonforthisisthat:
. YAS1 aS2
=aXAS1+S2 =aXAS1+Km- XAS1 =aKm =S1m Question 6.
a)
(1) A sends a request to B with A’s ID and a nounce Na encrypted with Ka
(2) B sends a request to the KDC with two blocks of data, one is the data just received from A, the second is B’s ID and a nounce Nb encrypted with Kb.
(3) KDC sends two blocks to B, one is session key Ks, A’s ID and nounce Nb encrypted with Kb, another is session key Ks, B’s ID and nounce Na encrypted with Ka.
(4) B sends the second block received from KDC to A
b)
This scheme has 4 steps, whereas scheme in lecture has 5 steps.
c)
The new scheme has the same degree of security with scheme in lecture.
d)
The advantage of this scheme is that if B doesn’t want the connection with A, then in the new scheme, the KDC doesn’t need to participate in the process. KDC involved only when B accepts the A’s request. Another is that the new scheme has one fewer step.
e)
KDC doesn’t need to store key information. User A and B need memory to store the session Key Ks.
Appendix
Code for Question1(a)
p = 196065871
q = 102305491
n=p*q
al = (p – 1) * (q – 1) import fractions
for i in range(2, al):
if fractions.gcd(i, al) == 1: break
print(n) e=i
print(e)
getInverse = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or getInverse(n, A % n, t, s - A // n * t, N or n), -1)[n < 1]
print(al)
d = getInverse(e, al)
print(d)
print(fractions.gcd(al, d * e))
Code for Question1(b)
p=
14083359469338511572632447718747493405040362318205860500297
736061630222431052998057250747900577940212317413063
q=
10513733234846849736873637829838635104309714688896631127438
692162131857778044158273164093838937083421380041997
n=p*q
al = (p - 1) * (q - 1) import fractions
for i in range(2, al):
if fractions.gcd(i, al) == 1: break
print(n) e=i
print(e)
getInverse = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or getInverse(n, A % n, t, s - A // n * t, N or n), -1)[n < 1]
print(al)
d = getInverse(e, al)
print(d)
print(fractions.gcd(al, d * e))
def mul(a, b, m):
for i in range(b):
a = (a * a) % m return a
m=
52765408864610854036298239004401986385255338175683906473958
95077673310897832541997323026747184971251245868225627887669
53
k = 13
mb = (m * pow(k, e, n)) % n
print('p: %d\n q: %d\n n: %d\n e: %d \n d: %d\n' % (p, q, n, e, d))
print('al: %d' % al)
print('mb: ' + str(mb))
signedMb = pow(mb, d, n)
unBlind = (signedMb / (k % n)) % n print('signedMb: %d' % signedMb) print("unblind: %d" % unBlind) directSign = pow(m, d, n)
print('directSign: %d' % directSign)