2. (40 POINTS 20 POINTS each) Rivest Shamir Adleman (RSA) is an asymmetric encryption algorithm. As it employs both public and private keys, it is possible to use RSA to authenticate a message by generating a digital signature. Assume that Alice and Bob use RSA to exchange a signed message. This question is about how Alice and Bob can fool each other while using RSA system for digital signature.
2.A.) (20 POINTS) Read the first RSA example at section 10.6.2.1 of your textbook, where Alice tricks Bob. Give another example of the same trick explained in this example. Please explain your steps clearly.
10.6.2.1 RSA Digital Signatures Section 9.3.2 discussed the RSA system. We observe that using it to authenticate a message produces a digital signature. However, we also observe that the strength of the system relies on the protocol describing how RSA is used as well as on the RSA cryptosystem itself. First, suppose that Alice wants to trick Bob into signing a message m. She computes two other messages m1 and m2 such that m,m2 mod nm. She has Bob sign m1 and m2. Alice then multiplies the two signatures together and reduces mod nBob, and she has Bob's signature on m. (See Exercise 8.) The defense is not to sign random documents and, when signing, never sign the document itself; sign a cryptographic hash of the document [888] EXAMPLE: Let nAlice-95, eAlice-59, dAlice-11, nBob = 77, eBob 53, and dBob 17, Alice and Bob have 26 possible contracts, from which they are to select and sign one. Alice first asks Bob to sign contract F (05): 0517 mod 77 3 She then asks him to sign contract R (17): 1717 mod 77 19 Alice now computes 05 x 17 mod 77- 08. She then claims that Bob agreed to contract 1 (08), and as evidence presents the signature 3 x 19 mod 77 = 57. Judge Janice is called, and she computes 5753 mod 77- 08 Naturally, she concludes that Bob is lying, because his public key deciphers the signature. So Alice has successfully tricked Bob A second problem [32] demonstrates that messages that are both enciphered and signed should be signed first, then enciphered. Suppose Alice is sending Bob her signature on a confidential contract m. She enciphers it first, then signs it: Alice Bob mod n Bob Alice and sends the result to Bob. However, Bob wants to claim that Alice sent him the contract M. Bob computes a number r such that M mod n Bob . He then republishes his public key as (reBob, nBob). Note that the modulus does not change. Now, he claims that Alice sent him M. The judge verifies this using his current public key. The simplest way to fix this is to require all users to use the same exponent but vary the moduli 10.6.2.1 RSA Digital Signatures Section 9.3.2 discussed the RSA system. We observe that using it to authenticate a message produces a digital signature. However, we also observe that the strength of the system relies on the protocol describing how RSA is used as well as on the RSA cryptosystem itself. First, suppose that Alice wants to trick Bob into signing a message m. She computes two other messages m1 and m2 such that m,m2 mod nm. She has Bob sign m1 and m2. Alice then multiplies the two signatures together and reduces mod nBob, and she has Bob's signature on m. (See Exercise 8.) The defense is not to sign random documents and, when signing, never sign the document itself; sign a cryptographic hash of the document [888] EXAMPLE: Let nAlice-95, eAlice-59, dAlice-11, nBob = 77, eBob 53, and dBob 17, Alice and Bob have 26 possible contracts, from which they are to select and sign one. Alice first asks Bob to sign contract F (05): 0517 mod 77 3 She then asks him to sign contract R (17): 1717 mod 77 19 Alice now computes 05 x 17 mod 77- 08. She then claims that Bob agreed to contract 1 (08), and as evidence presents the signature 3 x 19 mod 77 = 57. Judge Janice is called, and she computes 5753 mod 77- 08 Naturally, she concludes that Bob is lying, because his public key deciphers the signature. So Alice has successfully tricked Bob A second problem [32] demonstrates that messages that are both enciphered and signed should be signed first, then enciphered. Suppose Alice is sending Bob her signature on a confidential contract m. She enciphers it first, then signs it: Alice Bob mod n Bob Alice and sends the result to Bob. However, Bob wants to claim that Alice sent him the contract M. Bob computes a number r such that M mod n Bob . He then republishes his public key as (reBob, nBob). Note that the modulus does not change. Now, he claims that Alice sent him M. The judge verifies this using his current public key. The simplest way to fix this is to require all users to use the same exponent but vary the moduli
