OSS signature scheme

• US 20020188846A1
• Filed: 02/01/2002
• Published: 12/12/2002
• Est. Priority Date: 05/03/2001
• Status: Abandoned Application

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Levy, Yaakov (Jordan)
• Application Number:
  US10/062,001
• Publication Number:
  US 20020188846A1
• Time in Patent Office: Days
• US Class Current: 713/170
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/68 Special signature format, e.g. XML format
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A method for digitally signing a message is described. The method includes providing a message digest (M_x, M_z), providing a modulus N, providing a number V in a ring Z_N, wherein for another number S in the ring Z_N, V·S²=1 in Z_N, solving the equation (M_x+X)²−V·y²=4·(M_z+z) in Z_N to produce x, y, and z, and assigning SIG as the signature of M_X, M_Z), wherein SIG includes (x,y). Related methods and apparatus are also described.

Claims

1. A method for digitally signing a message, the method comprising:

providing a message digest (M_X, M_Z);

providing a modulus N;

providing a number V in the ring Z_N, wherein for another number S in the ring Z_N, V·

S²=1 in Z_N;

solving the equation (M_x+x)²−

V·

y²=4·

(M_z+z) in Z_N to produce x, y, and z; and

assigning SIG as the signature of (M_X, M_Z), wherein SIG comprises (x,y).

2. The method according to claim 1 and wherein SIG comprises (x,y,z).

3. The method according to claim 1 and wherein the solving comprises the following:

a) choosing α and

β

in Z such that 0≦

α

<

β

<

2<sup>k−

1</sup> and gcd(α

,β

)=1 in Z;

b) choosing γ

in Z such that 2<sup>n−

k−

1</sup>≦

γ

<

2<sup>n−

k</sup> and β

|(α

·

N+γ

) in Z;

c) setting R equal to (α

·

N+γ

)/β

in Z;

d) setting T equal to −

(M_z·

R+M_xR<sup>−

1</sup>) in Z_N;

e) if β

=1 or T<

8·

γ

(in Z), setting U and W equal to 0 and continuing with step k;

f) setting D equal α

<sup>−

1</sup> in Z_β

;

g) setting A equal to N/β

in Z;

h) setting B equal to (T−

8·

γ

)/A in Z;

i) setting U equal to B·

D in Z_β

;

j) setting W equal to U·

R in Z_N;

k) setting C (T−

W)/γ

in Z;

l) setting z equal to U+β

·

C in Z_N;

m) setting x equal to T−

z·

R in Z_N; and

n) setting y equal to S·

(x+M_x+2·

R<sup>−

1</sup>) in Z_N, thereby producing x, y, and z.

4. The method according to claim 3 and also comprising:

providing a trusted computation device and a non-trusted computation device,

wherein step d) comprises performing a computation in the non-trusted computation device.

5. The method according to claim 4 and wherein the computation in the non-trusted computation device comprises a computation of R⁻

1.

6. The method according to claim 5 and wherein the computation in the non-trusted computation device is protected from tampering by performing a blinding method in the trusted computation device.

7. The method according to claim 6 and also comprising verifying a result of the computation in the non-trusted computation device.

8. The method according to claim 3 and wherein step a) comprises screening α

and β

.

9. The method according to claim 8 and wherein the screening comprises reducing α

and β

modulo 210.

10. The method according to claim 9 and wherein the reducing a and β

modulo 210 comprises;

computing gcd(210, (α

mod 210), (β

mod 210)) to produce a result; and

rejecting α and

β and

choosing another α and

β

if the result is not equal to 1.

11. The method according to claim 1 and wherein the solving comprises the following:

a) setting α

equal to 0;

b) setting β

=1;

c) choosing γ

such that 2<sup>n−

k−

1</sup>≦

γ

<

2<sup>n−

k</sup>;

d) setting T equal to −

(M_z·

γ

+M_x+γ

<sup>−

1</sup>) in Z_N;

e) setting z equal to T/γ

in Z;

f) setting x equal to T−

z·

γ

in Z_N; and

g) setting y equal to S·

(x+M_x+2·

γ

<sup>−

1</sup>) in Z_N,

thereby producing x, y, and z.

12. The method according to claim 11 and also comprising:

providing a trusted computation device and a non-trusted computation device,

wherein step d) comprises performing a computation in the non-trusted computation device.

13. The method according to claim 12 and wherein the computation in the non-trusted computation device comprises a computation of γ

<sup>−

1</sup>.

14. The method according to claim 13 and wherein the computation in the non-trusted computation device is protected from tampering by performing a blinding method in the trusted computation device.

15. The method according to claim 14 and also comprising verifying a result of the computation in the non-trusted computation device.

16. A message signer for digitally signing a message based on a message digest (M_X, M_Z), a modulus N, and a number V in the ring Z_N, wherein for another number S in the ring Z_N, V·

S²=1 in Z_N, the message signer comprising;

a solver for solving the equation (M_x+x)²−

V·

y²=4·

(M_z+z) in Z_N to produce x, y, and z; and

a signature assignor for assigning SIG as the signature of (M_X, M_Z), wherein SIG comprises (x,y).