We define a digital signature scheme which has two parameters: an integer k (the RSA modulus size) and an integer l.
I've attached the full problem, can you please show me how to solve it?
Problem 2.5, 10 points. We define a digital signature scheme DSk (, S, V) which has two parameters: an integer k (the RSA modulus size) and an integer l. The message space for the scheme is 10, 1 For any l-bit message M let Mj denote its ,I. Then the key generation, signing and verifying algorithms j-th bit. for J = 1, are as tollowS: Algorithm ViNcy)(M, X Algorithm SNd.y)(M) For j = 1, ,Ido Algorithm or.] =1,..,,Ido For b = 0.1 do EndFor Return X If (x(j)e mod NYlMy For j = 1, ,Ido Then flag 0 EndIf EndFor EndFor EndFor Return flag Return N, e, Y), (N, d,Y) Here s is the standard RSA key generation algorithm. The public scheme of our scheme consists of the RSA modulus N, the RSA public exponent e, and a 2 by I array Y each of whose entries is a random point in Zy. The secret key is the RSA modulus N, the RSA secret exponent d, and the same array Y. The size of N is k bits, The signature of M is a one-dimensional array X of size consisting of pre-images under RSANe of certain points in the two-dimensional array Y, one per column of Y, the choice of which row being made according to the corresponding bit in the message. Here is a piture for l = 4. On the left it pictures the array Y. On the right it pictures how you can think of the signature X of message M = 1001, namely as the inverses of certain points in the array on the left 0,3 Y0,4 Y1,1 Y1,2Y1,3Y1,4 X2X3 Show that this scheme is not UF-CMA secure. You adversary has to have uf-cma - advantage 1 and make at most two queries to the signing oracle. Problem 2.5, 10 points. We define a digital signature scheme DSk (, S, V) which has two parameters: an integer k (the RSA modulus size) and an integer l. The message space for the scheme is 10, 1 For any l-bit message M let Mj denote its ,I. Then the key generation, signing and verifying algorithms j-th bit. for J = 1, are as tollowS: Algorithm ViNcy)(M, X Algorithm SNd.y)(M) For j = 1, ,Ido Algorithm or.] =1,..,,Ido For b = 0.1 do EndFor Return X If (x(j)e mod NYlMy For j = 1, ,Ido Then flag 0 EndIf EndFor EndFor EndFor Return flag Return N, e, Y), (N, d,Y) Here s is the standard RSA key generation algorithm. The public scheme of our scheme consists of the RSA modulus N, the RSA public exponent e, and a 2 by I array Y each of whose entries is a random point in Zy. The secret key is the RSA modulus N, the RSA secret exponent d, and the same array Y. The size of N is k bits, The signature of M is a one-dimensional array X of size consisting of pre-images under RSANe of certain points in the two-dimensional array Y, one per column of Y, the choice of which row being made according to the corresponding bit in the message. Here is a piture for l = 4. On the left it pictures the array Y. On the right it pictures how you can think of the signature X of message M = 1001, namely as the inverses of certain points in the array on the left 0,3 Y0,4 Y1,1 Y1,2Y1,3Y1,4 X2X3 Show that this scheme is not UF-CMA secure. You adversary has to have uf-cma - advantage 1 and make at most two queries to the signing oracle
