Method and apparatus for compressing rabin signatures

1. A method for compressing a Rabin signature, s, for a user having a public key, n, comprising:

configuring a processor to perform the steps of;

compressing said Rabin signature using a continued fraction expansion of s/n, wherein said continued fraction expansion of s/n further comprises the steps of;

computing principal convergents, u i /v i , for i equal to 1 to k, of a continued fraction expansion of s/n, where k is a largest integer for which principal convergents are defined, where U i and v i are principal convergents, and where a greatest common denominator (s, n) ≠1;

establishing an index l, such that v l <√{square root over (n)}<v l+1 ; and generating a compressed Rabin signature (v l , m) for a message, m, using said continued fraction expansion of s/n.

2. The method according to claim 1 , wherein sv=u (mod n).

3. The method according to claim 1 , wherein |v|≦√{square root over (n)}.

4. The method according to claim 1 , wherein |u|≦√{square root over (n)}.

5. A method for decompressing a compressed Rabin signature (v, m) for a message, m, and user having a public key, n, comprising:

configuring a processor to perform the steps of:

applying a message formatting function, h, to the message, m, to computing h(m);

computing a value, t, as h(m)v 2 mod n;

obtaining a value, w, as a square root of the value, t;

computing a signature value, s, as w/v mod n; and

providing a decompressed signature (s,m).

6. The method of claim 5 , further comprising the step of generating an error if no integer square root exists.

7. A method for compressing an RSA signature, s, for a message, m, and a user having a public key (n, e), comprising:

configuring a processor to perform the steps of:

computing principal convergents, u i/v i , of for i equal to 1to k, a continued fraction expansion of s/n, where k is a largest integer for which principal convergents are defined, where u i and v i are principal convergents, and where a greatest common denominator (s, n)≠1;

establishing an index l, such that v l <n (1-1/e) ≦v l+1 ; and

generating a compressed RSA signature (v l , m) using said continued fraction expansion of s/n.

8. A method for decompressing a RSA signature (v, m) for a message, m, and a user having a public key (n, e), comprising:

configuring a processor to perform the steps of:

applying a message formatting function, h, to the message, m, to computing h(m);

computing a value, t, as h(m)v e mod n;

determining whether the values t or t-n have an e th root over integer values;

computing a value, w, as the e th root; and computing the decompressed signature (w/v mod n, m).

9. The method of claim 8 , further comprising the step of generating an error if no e th root exists.

10. A system for compressing a Rabin signature, s, for a user having a public key, n, comprising:

a memory; and

at least one processor, coupled to the memory, operative to:

compress said Rabin signature using a continued fraction expansion of s/n, wherein said processpr is further configured to perform said continued fraction expansion of s/n by:

computing principal convergents, u i/v i , for i equal to 1to k, of a continued fraction expansion of s/n, where k is a largest integer for which principal convergents are defined, where U i and v i are principal convergents, and where a greatest common denominator (s, n) ≠1;

establishing an index l, such that v l <√{square root over (n)}≦v l+1 ; and

generating a compressed Rabin signature (v l , m) for a message, m, using said continued fraction expansion of s/n.

11. A system for decompressing a compressed Rabin signature (v, m) for a message, m, and user having a public key, n, comprising:

a memory; and

at least one processor, coupled to the memory, operative to:

apply a message formatting function, h, to the message, m, to computing h(m);

compute a value, t, as h(m)v mod n;

obtain a value, w, as a square root of the value, t;

compute a signature value, s, as w/v mod n; and

providing a decompressed signature (s,m).

12. The system of claim 11 , wherein said processor is further configured to generate an error if no integer square root exists.