CODEWITHSUNDEEP
securityencryptioncryptographyrsapublic-key-encryption
noted
noted

Reputation: 67

RSA Algorithm Example

In this simplistic example suppose an authority uses a public RSA key (e=11,n=85) to sign documents. You wish them to sign your message (which is the number 42) but you don’t want them to know what they are signing so you use a blinding factor ”r” of 11. In your calculations you may wish to use the following results:

11 ∗ 35 = 1 mod 64
11 ∗ 31 = 1 mod 85

Show brief working.

1) What number should you give the authority to sign?

2) What number will the authority give back to you?

3) Extract the signature for 42 from this number.

4) Verify this answer by using the private key.

I've had a look and if someone could guide this example with me I'd be very appreciated.

Upvotes: 0

Views: 2628

Answers (1)

Iridium
Iridium

Reputation: 23721

The message m is 42, and blinding factor r is 11, so the value provided to the authority is m' calculated as:

m' = m * re mod N
m' = 42 * 1111 mod 85
m' = 62

The authority will sign this by calculating s' using:

s' = m'd mod N

Where d is the private exponent.

We must therefore calculate the private exponent which we know to be a value that satisfies the relation:

e * d = 1 mod ɸ(N)

Where ɸ is Euler's totient function. N is the product of two primes p and q per the definition of the RSA algorithm, and since N is small we can easily factor it to determine p = 5 and q = 17.

Thus by definition of ɸ:

ɸ(N) = (p-1)(q-1)
ɸ(N) = (5-1)(17-1) = 64

Using the provided results, we can therefore determine:

e * d = 1 mod ɸ(N)
11 * d = 1 mod 64
d = 35

So, the authority should return to us the blinded signature s' calculated as:

s' = m'd mod N
s' = 6235 mod 85
s' = 73

To calculate the signature we need to calculate s using:

s = s' * r-1 mod N

Here, r-1 is the inverse of r such that:

r * r-1 = 1 mod N

Again using the given results we can determine r-1 as:

r * r-1 = 1 mod N
11 * r-1 = 1 mod 85
r-1 = 31

So the calculation for s becomes:

s = s' * r-1 mod N
s = 73 * 31 mod 85
s = 53

Your question says to verify this using the private key, however signatures are verified using the public key, so that's what I shall do here:

To confirm that this is the correct signature, we verify that:

m = se mod N
m = 5311 mod 85
m = 42

We have thus shown that the signature is valid, since m = 42 - our original message.

Upvotes: 6

Related Questions