1. Digital Signature and Programming
Write a java program to solve the following questions. Submit your code along with outputs. Let
e = n = 12801889219865986943874426789172837719929575398179139903346 0102259322494388756606728373121043154809790249663472677206622549 2472049090344014040948783013844255405121563940725271958261549105 6895127372123401970340184655821416714383833567438594837829393436 445708175846840391647287652219983832401360628720836954408208209
be an RSA public modulus. Note the public key e = n.
A. Without factoring n, provide a message m together with its RSA signature σ such that m ends with 2017 in base 10. Show that σ is a valid signature.
B. Without factoring n, check that the exponent
e' = 999858280201913599008802868696830357098395840037288384624455 77041064925905995005216889007572898641811594513334409291762876864 91104489407462355371113514648093
is also valid to verify signed messages. Show at least 5 examples.
2. Pseudorandom
Consider the variation on the Blum Blum Shub generator (mod n = pq)
BBS*(s0){
L:=number of bits in n.
for I to L{
si = s2i-1 mod n
}
Return s1||s2||· · · ||sL
}
A. Show how to distinguish the output of BBS* from a truly random source, even without knowing L or n.
B. Suppose your are given the output of BBS*. Show that how could can you use your method to find L, n and s0.