Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-06-28
2003-04-22
Darrow, Justin T. (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S029000, C380S037000, C380S042000, C708S135000, C708S501000, C708S502000, C708S523000
Reexamination Certificate
active
06553120
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method for decorrelating data recorded on a medium exploitable by a processing unit.
2. Description of Background and Relevant Information
There are many known methods of data encryption or cryptography. They serve to encode data such that the latter can be read only by an authorised recipient who possesses a key. Their importance is developing simultaneously with information networks and their use can be expected to become widespread in accordance with legislation in force.
Some encryption methods can provide unconditional security, but call upon heavy technical means which slow down communications or make the key exchange management very costly, while others cannot even be used practically.
For instance, to encrypt a flow of clear messages, the Vernam encryption method requires a flow of keys of the same length. Synchronisation between the sender and receiver then becomes difficult to achieve.
The conditions for unconditional security were formalised in 1949 by Shannon, who was able to demonstrate on the basis of information theory that unconditional security requires that the key must be at least equal to the total size of the messages that can be encrypted without corruption.
Thus, an encryption operation is carried out to ensure the protection of data recorded on a medium exploitable by a processing unit and liable to be transmitted. For the encryption of a series of messages to be secure, it is necessary to make these operations independent over a small number of messages.
The main encryption function used at present is the digital data encryption standard (DES) adopted by the U.S. government. This function is based on the (sixteen-fold) iteration of simple functions following the so-called “Feistel” scheme. The purpose of the large number of iterations is to weaken the correlation between the encrypted messages.
The DES is described in many documents and in particular the publication entitled “Encryption, Theory and Practice” by Douglas STINSON (International Thomson Publishing).
To improve the reliability of encryption and to safeguard against exhaustive searches, it has been proposed to increase the length of the key, or even to introduce a decorrelation of order 1. This is what has been submitted by the authors of the following two articles: Advances in Cryptology—CRYPTO '96, 16
th
Annual International Cryptology Conference, Santa Barbara, Aug. 18-22, 1996, Proceedings no. Conf. 16, Aug. 18, 1996, Koblitz N (ED), pages 252-267 by KILIAN J. et al., and Advances in Cryptology—ASIACRYPT, Fujiyoshida, Nov. 11-14, 1991, no. Conf. 1, Nov. 11, 1991, Hideki Imai; Rivest R L; Tsutomu Matsumoto, pages 210-224 by EVEM S. et al.
However, such measures are not sufficient to protect against attacks made possible by the recently-developed linear and differential cryptanalysis techniques.
SUMMARY OF THE INVENTION
The object of the invention is thus to provide a data encryption method which provides optimal security and which can be implemented with relatively simple functions only requiring modest calculation resources.
To this end, the invention relates to a method for the cryptography of data stored on a medium exploitable by a computing unit in which the computing unit processes an input information x by means of a key to provide information F(x) encoded by a function F.
According to the invention, the function F uses a decorrelation module M
K
, of rank at least equal to two, such that F(x)=[F′(M
K
)](x), where K is a random key and F′ is a cryptographic function.
Generally speaking, a decorrelation module serves to transform a message x by the function M
K
involving a key, such that the distribution M
K
(x
1
), . . . , M
K
(x
t
) obtained from any t different messages with a random variation of the key has a uniform or quasi uniform distribution.
Such a decorrelation module can thus be employed within a data encryption device, possibly after an information dividing device which supplies fixed length data x
0
in response to the input information x.
The invention can be implemented so that t blocks of messages c
1
, . . . , c
1
coded by the function F do not give any statistical information on that function.
In different embodiments each having particular advantages, the invention has the following features according to any technically feasible combinations thereof:
the input information x is divided up into elements x
0
of fixed length,
the function F is of the form F(x)=F′(M
K
(x)),
the coding function F′ is divided up into two functions F″ and G″ and
F
(
x
)=
F
″(
M
K
(
G
″(
x
))),
the decorrelation module M
K
is inversible,
the decorrelation module is M
K
(x)=ax+b, where K=(a, b) with a≠0,
the decorrelation module is M
K
(x)=a/(x+b)+c, where K=(a, b, c) with a≠0,
the function F is a Feistel function applying n iterations each with a function Fi,
the decorrelation module M
K
is non-inversible,
at each iteration, F
i
(x)=F′
i
(M
K
(x)),
at each iteration, F
i
(x)=F″
i
(M
K
(G″
i
(x))),
M
K
(x)=k
1
+k
2
x+k
3
x
2
+ . . . +k
t
x
t−1
,
where K=(k
1
, k
2
, k
3
, . . . , k
t
).
REFERENCES:
patent: 5345507 (1994-09-01), Herzberg et al.
patent: 5448640 (1995-09-01), Kim et al.
patent: 6078663 (2000-06-01), Yamamoto
Kilian, J. et al., “How to Protect DES Against Exhaustive Key Search”, Advances in Cryptology—Crypto '96, 16th Annual International Cryptology Conference, Santa Barbara, Aug. 18-22, 1996. Proceedings, No. Conf. 16, Aug. 18, 1996, Koblitz, No. (ED), pp. 252-267, XP000626592.
Even, S. et al., “A Construction of a Cipher from a Single Pseudorandom Permutation”, Advances in Cryptology—Asiacrypt, Fujiyoshida, Nov. 11-14, 1991, No. Conf. 1, Nov. 11, 1991, Hideki Imai; Rivest R. L., Tsutomu Matsumoto, pp. 210-244, XP000473951.
Shepherd, S.J., “A High Speed Software Implementation of the Data Encryption Standard”, Computers and Security International Journal Devoted to the Study of Technical and Financial Aspects of Computer Security, vol. 14, No. 4, Jan. 1, 1995, pp. 349-357, XP000523914.
Centre National de la Recherche Scientifique
Darrow Justin T.
Greenblum & Bernstein P.L.C.
LandOfFree
Method for data decorrelation 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 for data decorrelation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for data decorrelation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3028398