Generating unique and unpredictable values

• US 6,078,667 A
• Filed: 10/10/1996
• Issued: 06/20/2000
• Est. Priority Date: 10/10/1996
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Johnson, Donald B.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/729,012
• Time in Patent Office: 1,349 Days
• Field of Search: 380/44, 380/46, 380/47
• US Class Current: 380/44
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

An integer for a private key is generated utilising a pair of components that are combined in a fixed predictable manner. The first component is generated from a sequencer such as a counter that generates non-repeating distinct value and the second component is generated in a random manner. By combining the components the integer has a unique and unpredictable value.

Claims

1. A method of generating an integer for use as a private key in a public key encryption scheme comprising the steps of utilizing as a first component an output from a sequencer to provide a unique element to said integer, utilizing as a second component a randomly generated integer, combining said first component and said second component to provide said integer, and incrementing said sequencer prior to generation of a subsequent integer, whereby each generation provides a unique and unpredictable integer for use as said private key.

2. A method according to claim 1 wherein said first and second components are concatenated.

3. A method according to claim 2 wherein said first component precedes said second component.

4. A method according to claim 1 wherein said second component is utilized to set said sequencer.

5. A method according to claim 1 wherein said output from said sequencer is permuted prior to utilization as said first component.

6. A method according to claim 5 wherein said permutation is performed by an encryption algorithm.

7. A method according to claim 1 wherein said sequencer is a counter that increments.

8. A method according to claim 7 wherein said counter increments uniformly.

9. A method according to claim 7 wherein said counter increments non-uniformly.

10. Apparatus for generating a private key for use in a public key encryption scheme comprising a counting device to provide a non-repeating progressively varying integer, and having a first output, a number generator to generate numbers in an unpredictable manner and having a second output and an arithmetic unit to receive said outputs and combine said integer and said number to produce a unique and unpredictable integer, an output device to retrieve said integer from said arithmetic unit for use as a private key and a control signal to increment said counting device prior to a subsequent operation of said output device.

11. Apparatus according to claim 10 wherein said arithmetic unit includes a shift register to receive said outputs.

12. Apparatus according to claim 11 wherein said outputs are concatenated.

13. Apparatus according to claim 10 wherein said arithmetic unit includes a permutating device and said first output is connected thereto.

14. Apparatus according to claim 13 wherein said permutating device is connected to said shift register.