Cryptography – Communication system using cryptography – Data stream/substitution enciphering
Reexamination Certificate
1999-05-17
2001-07-31
Peeso, Thomas R. (Department: 2132)
Cryptography
Communication system using cryptography
Data stream/substitution enciphering
C380S037000, C380S268000, C380S259000, C380S255000, C380S245000, C380S044000, C713S150000
Reexamination Certificate
active
06269164
ABSTRACT:
BACKGROUND OF THE INVENTION
This present invention relates generally to the field of cryptography and more specifically to a method of and system for producing a fast, secure stream or block cipher.
Current uses of cryptography for securing computer files, network communications, E-mail, electronic commerce and voice communications impose certain difficulties that the current art does not adequately address. Electronic media requires the standardization of the encryption methods used and also requires broad dissemination of these methods. Therefore, basing security on the secrecy of the method used is ineffective.
In the current art, the security of the encrypted message lies solely in the obscurity of the keys chosen, and is relatively unaffected by a potential adversaries knowledge of the method used. This obscurity is a difficult thing to do since the coded message or ciphertext as it is known in the art is a function, albeit complex, of the key. EK(M)=C, where E is the Encryption method, K is the key, M is the clear message and C is the ciphertext.
It is implicit in this that K, the key, can be solved for if E, M and C are known. This is bad since it should always be assumed that a message, M, can be compromised for any given C by means, other than mathematical, such as fraud, carelessness or espionage. Thus, it must be assumed that a potential intruder will have E, C and at least one M. If the Key can be solved for, all other messages encrypted with that key are compromised.
The current art addresses this problem by making the solution for K hard. In the best current methods, the solution for K is as difficult as the “Brute Force” approach discussed below. This is cold comfort since this hardness is based upon current knowledge of mathematical processes. Improvements in these processes have made ciphers, that were thought of as strong 10 years ago, suspect now in light of the new methods that have been developed. This suspicion is based upon known improvements, ones that have been published and shared. To postulate that these are the only new improvements is to say that no person or organization would keep such improvements, which they have developed, secret. This would be an optimistic view, if not down right naive.
Any cipher can be solved for by a brute force approach. This is where breaking the encryption method is ignored and every possible key is examined until one is found that solves for the plaintext. As long as the group of possible keys is large and no keys are significantly worse than others, a brute force approach is no real threat to a good key. This is because the group of possible keys can easily be large enough that computers many billions of times faster than today's machines would take more time than the life span of the universe to try a significant portion of the possible keys.
Key management is as important to security as the underlying cipher. The resistance of a cipher to a brute force attack is dependent on the size of the key space. This key space is the volume of possible keys and is a function of the key length. It is important that the secret keys selected be distributed evenly throughout this key space so that an attacker does not have a higher probability area of the key space to focus an attack on with a correspondingly higher probability of success.
Some keys are generated from pass phrases. These easily remembered groups of words and symbols are a mnemonic for the actual key used which can be quite long and garbled. Transforming these pass phrases into good keys is difficult to do well. Common phrases use only a small portion of the available characters and repeat an even smaller subset of those characters in predictable ways. A direct translation of phrase characters to key characters would produce weak keys.
BRIEF OVERVIEW OF THE STREAM CIPHER EMBODIMENT DISCLOSED HEREIN
This invention relates to the field of cryptography and more specifically to a method of producing a fast, secure stream or block cipher. In the case of stream ciphers, current art relies heavily on the use of pseudo-random number generators. These are numerical or sometimes physical constructs that produce “random” noise, which is then used to obscure the relationship between the key and the process or the enciphered message and the key or both. The ultimate example of this is the Russian “One Time Pad” method or OTP as it is known in the art. In this method, a group of randomly generated numbers is the key itself. This is a singular example in that it is the only method that can be proven to be secure. Unfortunately the constraints of the proof make the method logistically impractical as the key must be the same size as the message and each key can only be used once.
The current art seems to be based on the premise that some form of near random behavior is essential to a good cipher. This leads to a situation where an unattainable, poorly defined ideal is pursued as a condition for success. It does not logically follow that since truly random is a requirement in an OTP, that near random or pseudo-random should be ideal in another encryption method. Random is either a statement of how it was derived or an exclusive definition. No number or sequence can be proven to be random and may only be stated as having no known pattern or that it is the product of a known random process such as the decay of a radioisotope. If no number can be proven random, then surely no rational evaluation of another numbers “randomness” can be made.
The embodiments disclosed herein dispenses with the semantic difficulty stated above by defining the two requirements for secure encryption in productive terms.
The first requirement for this definitive method employs the use of a stochastic construct to generate arbitrary operators as opposed to pseudo-random operators. In this case, arbitrary operators are defined as:
A stream of numbers created such that their organization is arbitrary to any guide or pattern except the complex relationship between a method and an initial condition or “key”. Furthermore, that relationship shall be limited to sequential steps of “key permutation” based solely upon arbitrary characteristics of the current key state evaluated against an arbitrary, fixed criterion. This key permutation is the repeated scrambling of the key state in one chosen way of many possible ways that are all equally weighted. The actual way chosen at each step is the result of a decision made, based upon the last change choice and the current key state. This last choice returns a new choice according to an arbitrary function of the current relative condition of the key (a score table) versus a fixed, unchanging template (a position table) to produce the current key permutation choice. This current key permutation choice is the arbitrary operator described above and a new one is produced each time the key is scrambled. Since the arrangement of the available choices are a function of the current key state derived in an arbitrary way, the arbitrary operators generated are specific to the current key state and therefore to the sequential change of the key state from its initial condition to the current configuration and nothing else.
Care must be taken to assure that the permutation behavior is arbitrary and irreversible. In the preferred embodiment the above mentioned score table is actually a ranking table of the Sums of test permutations performed on the current key. These test permutations are similar in construction and magnitude to the real change choices available (one of which the key will be scrambled to) but they are intentionally constructed so that they would make changes to the key that the actual choices could not. This is an important component of arbitrariness. The decision on how to change the key should be made by evaluating changes that cannot be made. This breaks any direct relationship between the state of the key and the change behavior, which is entirely key dependent.
Irreversibility is achieved by using the Sum of the key values of each test permutation through
Jack Todd
Peeso Thomas R.
Shour Stephen C.
LandOfFree
Method of and system for encrypting messages does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of and system for encrypting messages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and system for encrypting messages will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455722