Apple files cryptographic systems patent relating to small form factor devices such as the iPod, cell phone or PDA
On December 28, the US Patent & Trademark Office published Apple’s patent application titled ‘Chaos generator for accumulation of stream entropy’ which was originally filed in mid 2005. Apple’s patent generally relates to cryptography and in particular to the generation of secure random numbers for use in cryptographic systems. Apple further notes that the patent’s method and apparatus is to provide random numbers of cryptographic strength that are suitable for use in cryptographic systems for small devices such as the iPod, cell phone, PDA or other such devices.
Apple’s Background
Since the advent of public-key cryptography, numerous public-key cryptographic systems have been proposed. Today, only three types of systems are still considered secure and efficient. These systems include integer factorization systems, discrete logarithm systems and elliptic curve cryptography (ECC) systems. The security afforded by integer factorization rests on the difficulty of factoring a large product of two prime numbers. The security of discrete logarithm systems rests on the difficulty of solving the discrete logarithm problem (DLP). The security of ECC systems rests on the difficulty of solving the elliptic curve DLP (ECDLP) problem, which amounts to finding a log in a group of points defined on an elliptic curve over a prime field. ECC’s advantage over other systems is that its inverse operation gets harder, faster, against increasing key length, making it suitable for portable devices having small form factors with limited power and memory.
Cryptographic systems, and particularly stream ciphers, often use pseudorandom number generators to provide sequences of random numbers. Such random number generators can produce, at most, only 2.sup.k different output values, where k is the number of bits used to represent internal state data. The pseudorandom number generator often is initialized in an arbitrary state of a repeating sequence of states (i.e., a cycle) as some function of a keyword or key phrase. Thus, an arbitrary initialization of a pseudorandom sequence may result in a short cycle or pattern of different output values that could repeat during a long message or session. These repeated patterns make pseudorandom number generators vulnerable to automated attacks. To prevent patterns from occurring, longer sequences (large k values) can be used. However, for devices having small form factors (e.g., media players, mobile phones, etc.), power and memory constraints limit the length of the random number sequences that can be generated, resulting in an increased risk that detectable patterns will be generated.
Therefore, what is needed is a system, method and apparatus for providing random numbers of cryptographic strength that are suitable for use in cryptographic systems for small devices.
Summary of Embodiments
A chaos generator for accumulating stream entropy is disclosed. The chaos generator includes a random-source coupled to an entropy accumulator that is configurable for generating a binary random input sequence. The entropy accumulator is configurable for accumulating entropy of the input sequence and providing a binary random output sequence based on the accumulated entropy. The binary random output sequence is reduced by a modular reduction operation having a modulus that is set equal to a cryptographic prime (e.g., the order of an elliptic curve). The number of iterations performed by the entropy accumulator on the binary random input sequence is selected to provide a binary random output sequence having a desired cryptographic strength. The chaos generator can be part of a signing and verification system that uses fast elliptic encryption for small devices.
To clarify what small devices could be covered by Apple’s patent, Apple further notes that both the “the challenging device and signing device can be any type of memory constrained communication device, including but not limited to, computers, network devices, media players (e.g., music recorders/players), smart cards, email devices, instant messaging devices, mobile phones, digital cameras, personal digital assistants (PDAs), docking stations and the like.
Patent Figures: FIG. 1 is a block diagram of one embodiment of a chaos generator. FIG. 2 is a block diagram of one embodiment of an entropy accumulator.
Apple’s patent covers the following subject matter: Chaos Generator Overview, Entropy Accumulator System, Chaos Generator Process Flows, Signature Signing and Verification System, Curve Parameter Structure and Entropy Estimation for Counter Sequence.
Apple lists the inventors of this patent as being Richard E. Crandall, Douglas P. Mitchell, Scott Krueger and Guy Tribble. For the record, Apple’s patent application notes that “this application is related to U.S. application Ser. No. 11/051,441, filed Feb. 3, 2005, entitled “Small Memory Footprint Fast Elliptic Encryption,” which application is incorporated by reference herein in its entirety.”
NOTICE: MacNN presents only a brief summary of patents with associated graphic(s) for journalistic news purposes as each such patent application and/or grant is revealed by the U.S. Patent & Trade Office. Readers are cautioned that the full text of any patent applications and/or grants should be read in its entirety for further details.
Written and researched by Neo.
