Wednesday, October 06, 2010

Identity Based Signature

Adi Shamir (Identity-based cryptosystems and signature schemes. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 47–53.) described how one can use his/her identity to sign a message.


Setup

Let:

m - Message
i - Identity
n - Composite of two large primes
f - One way function

ge = i (mod n)

Note: Think of this as RSA decryption of an encryption of i which is g.

Where e is a large prime that is relatively prime to Φ(n)

g - private
e - public

Signature

t = re (mod n) , r - random

s = g∙rf(t,m) (mod n)

<s,t> is the signature value sent to the receiver of message m.

Verification

Test:

se == i∙tf(t,m) (mod n)

This works because

se == ge∙re∙f(t,m) (mod n)

Since t = re and ge = i :

=> se == i∙tf(t,m) (mod n)

No comments: