1
$\begingroup$

I've been given a set of message-signature pairs to decrypt using a public RSA key I set up. I need to sort through the decoded messages, and find which of those have a valid signature. My public key is

e=13

and

m=23988477718194197355263570318118557072073635564327068738051383543307247873821867

My code so far comprises of

decryptionRSA[x_?IntegerQ, d_?IntegerQ, m_?IntegerQ] := PowerMod[x, d, m]; 
SetAttributes[decryptionRSA, Listable]
messages2 = Table[i -> decryptionRSA[messages, d, m], {i, messages}]

It then outputs messages2, which is too big to copy onto here. Note that: d=PowerMod[e,-1,m]. A message signature pair will come in the form (a,b), with b being the signature. To tell if the pair is valid and authentic, using the public key, you compute z=PowerMod[b,e,m] and if this equal to a then the pair is valid. However, I don't know how I would verify this with a large quantity of data, would I use the Table function?

$\endgroup$
0
1
$\begingroup$

This answer will try to address a number of shortcomings/inconsistencies in the body of the question and finally suggest a possible solution.

Issues

  1. In the definition of the function decryptionRSA[] the second parameter, namely parameter d, is not an actual parameter. According to the body of text, d=PowerMod[e,-1,m], where e and m are given.
  2. Assigning the attribute Listable to symbol decryptionRSA will allow it to thread over lists. Applying a listable function over a list of pairs eg f[{{a,1},{b,2},...}] does not produce {f[a,1],f[b,2],...} which is the desirable behavior, but rather {{f[a],f[1]},{f[b],f[2]},...}.

A solution

Assuming that messages is a list containing pairs of message and signature, then the following code will produce a list of booleans, where True would indicate the position of a valid pair in the original list.

d = PowerMod[e,-1,m]
mask = Map[(
  #[[1]] == PowerMod[#[[2]], d, m] 
 )&,messages]

The valid pairs can be retrieved using eg pos = Position[mask,True] and then valids = Extract[messages,pos].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.