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: 14083359469338511572632447718747493405040362318205860500297736061630222431052998057250747900577940212317413063
q: 10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997
ii. the public key e be smallest valid public key.
n = p * q = 148068684511079402378185544670910028396429695657590390935242421034422471481084191890163030094123629499752941095042782115712555821328518268547699617479197158668660448059195876291281822260258035910071417381842181336406811
φ(n)=(p−1)⋅(q−1) = 148068684511079402378185544670910028396429695657590390935242421034422471481084191890163030094123629499752941070445689411527194511822432719961571108129120151566168820322767652529201613163101705495229677866818547638951752
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 = 59227473804431760951274217868364011358571878263036156374096968413768988592433676756065212037649451799901176428178275764610877804728973087984628443251648060626467528129107061011680645265240682198091871146727419055580701
iv. A random message m of length at least 100 digits.
m = 527654088646108540362982390044019863852553381756839064739589507767331089783254199732302674718497125124586822562788766953
v. A blinded message mb.
take a random blind number k = 13
compute the blinded message as
mb = m * pow(k, e) mod n = 195914269535679578276992820546614267309406102772642046864356407107455662318893801581205857004254953078883215109805529648280229
vi. Signature of m through blinded process.
signs the blinded message with private key
signed_mb = mb d mod n = 82983905868642969743150750177498291750264933872464443116221481338024761410568983396705482581518218070619538482077756654865162073357811502953289319459292215221053767877669448068130342605503033607921774411775774555719421
unblind the signed blinded message
unblind = signed_mb / k mod n = 6383377374510997908250323066111276525170882013707856333216058846309324127171400175935842424093606542609459282769357478070134593967764289118733361026649019675194021758471027892274540880359951229515095583474345465348096
vii. Direct signature of m using the private key.
m d mod n = 6383377374510997672550057705961407057712687220958803316632421641386520108505306415131190967809093697739964498621365896528089390258293192534868409189176324247773366759820726774471564815807925662147828800905828811978417
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.
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 = yAk mod q
= ak XA mod q.
· 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
· The signature is valid if V1 = V2.
The reason for this is that:
· YAS1 a S2
= a XAS1 + S2 = a XAS1 + K m – XA S1 = a K m = 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 = 14083359469338511572632447718747493405040362318205860500297736061630222431052998057250747900577940212317413063 q = 10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997 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 = 527654088646108540362982390044019863852553381756839064739589507767331089783254199732302674718497125124586822562788766953 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) /docProps/thumbnail.jpeg