Question 1.
(a) (<f, e, n) = (303703, 7,1065023) w = 485441
Signature s = wd = 485441303703 = 105153 mod 1065023
The signature can be verified as se = 1051537 = 485441 mod 1065023
(b) (x,q,p,y) = (60221,2,555557,552508), r = 12345 a = qr = 212345 = 148533 mod 555557
r-1 ee 161289 mod 555556
b = r~x * (w -a*x) = 161289 * (485441 - 148533 * 60221) = 508404 mod 555556 Signature is sent together with message as (w, (a,b)) = (485441, (148533,508404)) It can be verified without the knowledge of private key x: qw = 248544l = 270960 mod 555557
ya *ab = 55250814SS33 * 148533508404 = 270960 mod 555557
Question 2.
If s-[ and sa are signatures of mi and mj, we can compute the signature of m = m\m% mod ri as s = sjs2 mod n.
Since 1773 = m-j * mo, we can compute S3 as
S3 = s\S2 mod n = 192 ■ 454 mod 581 = 18
We can use the same principle for finding signature £4 for 7714 = 508, as 33 ■ 33 = 508 mod 581:
S4 = s\ ■ s\ = 192 ■ 192 = 261 mod 5S1
If s is a signature of m. then s~l is a signature of m-1. We see that 6_1 mod 5S1 = 97, therefore
5s = sf1 mod m = 454-1 mod 5S1 = 398
Question 3.
Using the procedure from the lecture:
h = k-2 = (fc-1)2 = 4575- = 25514 mod 23737
Public key (h, n) = (25514. 29737).
si = r(i + w^ modn
S\ = \- (f^ + 111) mod 29737
S\ = 1 ■ 2~* ■ (2020 - 111-1 + 111) mod 29737
Si = I ■ 14569 ■ (2020 ■ 27058 +111) mod 29737
51 = 15201 mod 29737
52 = T ' S - 1U) mod 29737
53 = 13■ 2_* ■ (2020 ■ 111-1 - 111) mod 23737
51 = 13 ■ 14869 ■ (2020 ■ 27058 - 111) mod 29737
52 = 17748 mod 29737
Signature (u/.Si.Sfc) = (2020,15201,17748).
Signature "verification:
w = Si2 — h ■ S%2 mod rt
2020 - 152012 - 25514 ■ 177482 mod 29737
2020 = 2020 mod 29737
Since this holds the verification was successful.
Recovery of secret message:
M=(gi+f-i-a» mod"
M= isaou-iffi-iras mod 29737
w = 15201+^1^8   mod 29737
uj = 2020 ■ (15201 + 4575 ■ 17748)-1 mod 29737
w = 2020 ■ (554)_1 mod 29737
w = 2020 ■ 3489 mod 29737
u.f = 111 mod 29737
From the signature message w = 111 was recovered.
Question 4.
The final step to obtain the signature would be   s = Y\ ^ mod. N.
t=i
n
Since d = ^^dj, we need all n parties to recover the original private exponent d, therefore this i=l
scheme is correct only when t = n.  It also holds that mdi ■ md> = mdi+di mod Nt therefore
s = md =     mdi mod Ar =     st mod N.
; 1 ■ 1
Question 5.
To preserve the security of Lamport one-time signature scheme, for each index i in ytj in the secret key, we can use either the value associated with or bot not both. Otherwise, the attacker could exploit the knowledge of both of these values for some i and craft a valid signature for a message with an arbitrary bit on the t-th position,
There are 2e = 64 possible 6-bit messages in total. For each message, we need a unique combination of the values from the secret key and match them with values in the public key for verification. Choosing 4 out of 8 ytj gives us
C(n'k) = k\tn-k)\ = 4!(S8-4)! = ?°
unique combinations (subsets) of the key values. All we need to do is assign every possible 6-bit message to one of the TO combinations in a deterministic way, so the verifying party can replicate this process with the public key.
There might exist a more efficient solution, but the most straight-forward one is to order the messages from 000000 to 111111. then we use some deterministic subset selection algorithm to select 64 unique subsets of 4 values from the 8 values in the secret key. order them in a deterministic way by utilizing
their indices (for simplicity, we can change the indices to 1 < i < 8) and map each of the 64 possible messages to one of the subsets.
The verification process is similar, the verifying party first creates the mapping of the messages to subsets of the values from the public key using the same algorithm as the signing party used for this purpose, which ensures there arc equivalent elements in the subsets and preserves mapping of the messages to the subsets with respect to the indices of the elements. For example, if the algorithm mapped the message 100001 to a signature {y\, j/a,Jft,l/s}, then the same algorithm needs to map the same message to {21,22, 25,23} values from the public key during verification.
The verifying party then computes f{yt) for each value in the signature and checks whether the four values match with the corresponding values in the table created from the public key in the previous step (mapping of possible messages to combinations of Zi).
This scheme preserves the security properties of the original Lamport scheme. There are no two different messages, which would get mapped to the same values from the secret key, In other words, there are at most three identical values out of four values in the signature, therefore the attacker would have to reverse the one-way function / for at least one value in the public key to forge a M'j;tnuu:i ■ o| nut die:' niossn^o.
Question 6.
{q,p,y) = (2,567899.300210) {wu (ai, bi)) = 172459, (226741,13448) (a3, bi)} = 172519, (331901, 326010) (u>3, (q3, bS) = 359406, (390725,789S1) (u>4, (04, &4>) = 456149. (144902,184381) (tub, (a5, bs}) = 459379, (43870,540485)
We can see bi and f?2 are not invertible mod p — 1 bur frj1 = 141455 mod 5G789S. so we can write the following equations from the definition b = r-1 * (w — a * x) with the substitution r± = 3 * r$ mod p — 1: r% * 63 =     — 03 * x
3 * ^3 * hi =W4—di*X
3 * (uij — a3 * t) * (b^)-1 * &4 = uj4 — «4 * a:
3 * (&3}-1 * 64 * uj3 — 3 * (fe)-1 * 64 * 03 * 2; = tt'4 — 04 * x
3 * (&3)_l * 64 * u>3 — ii;4 = x * (3 * (&3)-1 * &4 * 03 — 04}
X = (3 * (£>3)-1 * 64 * w3 —        * (3 * (&3)_1 * 64 * Qg — 04)_1
r = (3*141455*184381*359406-456149)*(3*141455*18438U390725-144902)-1 = 56789 mod p-1 Now we can count r-3 = (vis-a^x)*^)'1- = {359406-390725*56789)* 141455 = 160543 mod 567898 If we perform a simple check using a = qr mod p for all five signatures, we see it works (we have to get the original rt = 160543 * 9_1 = 333337 mod p-1 first).
So we can finally compute the signature of UCO 485441 and add it to the list instead of record 5
(as the list is ordered): aa = if* = 2s*rs = 29*160543 = 43870 = aE mod p
6e = r^1 * (wa -aQ^x) = 88871 * (485441 - 43870 * 56789) = 240545 mod 567898
So add there 485441, (43870,240545) which can be then verified as:
ya*ab = 3002104 38 ™ * 43870240345 = 225548 = qw = 248£441 mod p