Method and a system for a quick verification rabin signature scheme

1. In a computing device for computing digital signatures, a method comprising: generating, via a computing device, a value P and a value Q, wherein P and Q are distinct prime numbers; computing, via a computing device, a value public key N, wherein public key N is equal to the product of values P and Q; accessing, via a computing device, a value MQ, wherein MQ is a number that has a square root in modular arithmetic when the modulus is public key N; and wherein accessing the value MQ comprises: computing a hash value MH, wherein MH is a result of a hash function with an original message MO as an argument; computing a redundancy value MR, wherein MR is a result of a redundancy function with MH as an argument; and transforming MR into the value MQ; computing, via a computing device, a value signature S, wherein signature S is equal to the square root of MQ in modular arithmetic when the modulus is public key N; computing, via a computing device, a value q, wherein q is equal to the largest integer less than or equal to the quotient of signature S squared divided by public key N; and storing signature S, public key N, and value q in a storage medium of the computing device; performing, via the computing device, a message verification, using signature S, value MQ, public key N and value q; reporting, via an output device of the computing device, a message verification status indicating the message verification passed or failed based on the message verification performed.

2. The method of claim 1 , wherein transforming MR into the value MQ comprises performing an exclusive-or function with MR and an initial vector as arguments.

3. In a computing device for computing digital signatures, a method comprising: accessing, from a storage medium of the computing device, a value N, wherein N is the product of values P and Q, wherein P and Q are distinct prime numbers; accessing, from the storage medium of the computing device, a value MQ, wherein MQ is a number that has a square root in modular arithmetic when the modulus is N; and wherein accessing the value MQ comprises: computing a hash value MH, wherein MH is a result of a hash function with an original message MO as an argument; computing a redundancy value MR, wherein MR is a result of a redundancy function with MH as an argument; and transforming MR into the value MQ; accessing, from the storage medium of the computing device, a value S, wherein S is the square root of MQ in modular arithmetic when the modulus is N; accessing, from the storage medium of the computing device, a value q, wherein q is the largest integer less than or equal to the quotient of S squared divided by N; and performing, via the computing device, a message verification, using S, MQ, N and q.

4. The method of claim 3 , wherein performing the message verification comprises executing arithmetic algorithms wherein the arithmetic is all non-modular arithmetic.

5. The method of claim 3 , wherein performing the message verification comprises:

computing a value A equal to the square of S minus the product of q and N; and

reporting the message verification failed when A is not equal to MQ and reporting the message verification passed when A is equal to MQ.

6. The method of claim 5 , wherein computing the value A comprises:

dividing A and MQ into words;

computing each word of A sequentially, wherein the words are computed in order of increasing significance; and

terminating the computing for each word of A not equal to the word of MQ having the same significance.

7. The method of claim 3 , wherein transforming MR into the value MQ comprises performing an exclusive-or function with MR and an initial vector as arguments.

8. An article of manufacture comprising: a machine-accessible non-transitory storage medium including data that, when accessed by a machine, cause the machine to perform operations comprising, generating a value P and a value Q, wherein P and Q are distinct prime numbers; computing a value N, wherein N is equal to the product of values P and Q; accessing a value MQ, wherein MQ is a number that has a square root in modular arithmetic when the modulus is N; and wherein accessing the value MO comprises: computing a hash value MH.

9. The article of manufacture of claim 8 , wherein transforming MR into the value MQ comprises performing an exclusive-or function with MR and an initial vector as arguments.

10. The article of manufacture of claim 8 , wherein the machine-accessible medium further includes data that causes the machine to perform operations comprising:

writing q on a mass storage media memory.

11. An article of manufacture comprising: a machine-accessible non-transitory storage medium including data that, when accessed by a machine, cause the machine to perform operations comprising, accessing a value N, wherein N is the product of values P and Q, wherein P and Q are distinct prime numbers; accessing a value MQ, wherein MQ is a number that has a square root in modular arithmetic when the modulus is N; and wherein accessing the value MQ comprises: computing a hash value MH, wherein MH is a result of a hash function with an original message MO as an argument; computing a redundancy value MR, wherein MR is a result of a redundancy function with MH as an argument; and transforming MR into the value MQ; accessing a value S, wherein S is the square root of MQ in modular arithmetic when the modulus is N; accessing a value q, wherein q is the largest integer less than or equal to the quotient of S squared divided by N; and performing a message verification, using S, MQ, N and q.

12. The article of manufacture of claim 11 , wherein performing the message verification comprises executing arithmetic algorithms wherein the arithmetic is all non-modular arithmetic.

13. The article of manufacture of claim 11 , wherein performing the message verification comprises:

computing a value A equal to the square of S minus the product of q and N; and

reporting the message verification failed when A is not equal to MQ and reporting the message verification passed when A is equal to MQ.

14. The article of manufacture of claim 13 , wherein computing the value A further comprises:

dividing A and MQ into words;

computing each word of A sequentially, wherein the words are computed in order of increasing significance; and

terminating the computing for each word of A not equal to the word of MQ having the same significance.

15. The article of manufacture of claim 11 , wherein accessing the value q comprises accessing the value q from a mass storage media memory.

16. A system for computing digital signatures comprising: a processor; a memory coupled with the processor; a machine-readable non-transitory storage medium coupled with the processor, wherein instructions stored upon the machine-readable non-transitory storage medium, when executed by the processor, cause the processor to perform a method comprising: accessing a value N, wherein N is the product of values P and Q, wherein P and Q are distinct prime numbers; accessing, from the machine-readable non-transitory storage medium of the system, a value MQ, wherein MQ is a number that has a square root in modular arithmetic when the modulus is N; and wherein accessing the value MQ comprises: computing a hash value MH, wherein MH is a result of a hash function with an original message MO as an argument; computing a redundancy value MR, wherein MR is a result of a redundancy function with MH as an argument; and transforming MR into the value MQ; accessing, from the machine-readable non-transitory storage medium of the system, a value S, wherein S is the square root of MQ in modular arithmetic when the modulus is N; accessing, from the machine-readable non-transitory storage medium of the system, a value q from the memory, wherein q is the largest integer less than or equal to the quotient of S squared divided by N; performing, via the processor of the system, a message verification, using S, MQ, N and q; and reporting, via an output device communicably interfaced with the system, a message verification status indicating whether the message verification passed or failed based on the message verification performed.

17. The system of claim 16 , wherein performing the message verification comprises:

computing a value A equal to the square of S minus the product of q and N; and

reporting the message verification failed when A is not equal to MQ and reporting the message verification passed when A is equal to MQ.

18. The system of claim 17 , wherein computing the value A further comprises:

dividing A and MQ into words;

computing each word of A sequentially, wherein the words are computed in order of increasing significance; and

terminating the computing for each word of A not equal to the word of MQ having the same significance.

19. A system to verify digital signatures comprising: a processor; a memory coupled with the processor; a non-transitory storage medium; and a message verifier to run on the processor and having functionality to; access, from the non-transitory storage medium of the system, a value N, wherein N is the product of values P and Q, wherein P and Q are distinct prime numbers; access, from the non-transitory storage medium of the system, a value MQ, wherein MQ is a number that has a square root in modular arithmetic when the modulus is N; and wherein accessing the value MQ comprises: computing a hash value MH, wherein MH is a result of a hash function with an original message MO as an argument; computing a redundancy value MR, wherein MR is a result of a redundancy function with MH as an argument; and transforming MR into the value MQ; access, from the non-transitory storage medium of the system, a value S, wherein S is the square root of MQ in modular arithmetic when the modulus is N; access, from the non-transitory storage medium of the system, a value q from the memory, wherein q is the largest integer less than or equal to the quotient of S squared divided by N; perform a message verification, using S, MQ, N and q; and report, via an output device communicably interfaced with the system, a message verification status indicating whether the message verification passed or failed based on the message verification performed.

20. The system of claim 19 , wherein the message verifier to perform the message verification comprises the message verifier to:

compute a value A equal to the square of S minus the product of q and N; and

report the message verification failed when A is not equal to MQ and report the message verification passed when A is equal to MQ.

21. The system of claim 20 , wherein the message verifier to compute the value A comprises the message verifier to:

divide dividing A and MQ into words;

compute each word of A sequentially, wherein the words are computed in order of increasing significance; and

terminate the computing for each word of A not equal to the word of MQ having the same significance.