Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-09-24
2001-05-01
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
Reexamination Certificate
active
06226382
ABSTRACT:
The present invention relates to a process for implementing a communications protocol between two processing devices, at least one of which is a portable storage device such as a smart card.
BACKGROUND OF THE INVENTION
Data confidentiality is currently a major concern. It is clear that data in all their forms have intrinsic value that is often difficult to evaluate. Much of the wealth of a corporation or even a country resides in this growing volume of paper and electronic documents that condense its past, present, and even future activities. Paper documents that justified protection were hidden, concealed in locations that were made as difficult as possible to access. The spread of e-mail and electronic filing renews the problem and spurs a search for solutions to the problem.
Answers in this field are based on the concept of secret data being shared by a group of individuals at a given time. The processes implemented to date were based on simple operations that could be carried out on any device capable of elementary operations (binary addition, shifting, permutations, etc.).
The very nature of these processes implies lengthy and particularly painstaking design to build a machine whose logic is virtually error-free and whose errors are in any event never fatal. The confidentiality or secrecy of the data, on which all system security depends, would indeed be broken if the data transmitted between the devices were not kept secret, and this disclosure would then cause the security of the system to fail.
The design of effective protocols thus represents a particularly large investment in time and resources. Also, there is a relationship between maximum security and the quantity of information to be processed.
BRIEF SUMMARY OF THE INVENTION
The present invention solves this problem and in particular eliminates manufacturing shortcoming due to the fact that system reliability does not rest solely on the secrecy of the information held in this equipment.
According to the invention, it is proposed to divide this constraint between the secret held and the processing accomplished, namely the protocol itself.
For this purpose, according to the invention, the process enables secret-key cryptographic protocols securely contained in (hardware or software that are) dedicated to the performance of complex calculations (for example operations employing modular calculation) in the framework of public-key cryptographic protocols (DH, El Gamal, Schnorr, Fiat-Shamir, etc.).
Devices equipped with calculation resources for performing complex operations (such as modular calculation) are currently known; for example circuits such as the ST16CF54 circuit by the Societe Thomson, 83C852/5 by the Philips Company, or SLE 44CP200 can be cited.
According to the invention, such a resource is used judiciously, namely using operations that take little time but whose effects on data are effective in terms of encrypting and keeping secret the information processed. The principle is to combine operations that call simultaneously on resources dedicated to complex operations in the device itself, whatever its nature (simple application-oriented computer of the 8051 or 6805 type, processors of the 80x86 or 680x0 family, advanced processors Pentium, Alpha chips, SUN, or RISC), and parallel processors (Hypercube for example) combining cleartext information with a secret key to obtain an enciphered message that only a person possessing the secrecy protocals can decipher.
Thus, the invention proposes a highly securitized system wherein modular calculation can have a large number of bits, for example 80, 160, or 512 or more, requiring only the combination of two operations.
The present invention relates in particular to a process for implementing a secret-key protocol between two processing devices, at least one of which is a portable storage device, principally characterized by comprising the following stages:
equipping the devices of a digital processing circuit able to perform operations of the modular calculation type to carry out operations such as modular multiplication,
using this processing circuit to implement a secret-key enciphering function composed of a sequence of reversible operations comprising at least the combination of two operations, one of the modular calculation type and the other in binary logic,
applying this function either to messages intended for transmission to encipher or sign them, or to received messages to decipher them.
To process messages of any length, each message is first divided into q blocks×N bits.
According to another aspect of the present invention, the secret-key enciphering function comprises a combination of two operations, one of which is permutation that uses modular multiplication and the other an OR-exclusive logic operations where f is such that:
f
(
x
)=(
x⊕K
2
)*
K
1
mod
n
wherein
x represents a block of N message bits
K
1
and K
2
represent a first and second secret key with N bits,
n is an odd number of N bits
⊕ is an OR-exclusive operation
* is a modulo multiplication operation n
According to another feature of the invention, the user can choose K
1
≠K
2
or K
1
=K
2
.
According to another feature of the invention, when a device is sending messages, it performs a first operation on the message by applying the chosen function f iteratively to each block x
i
.
Preferably, an iteration number p equal to at least 4 is used.
Thus, according to a first embodiment, devices A
j
and A
k
communicate with each other according to the following protocol:
device A
j
enciphers each block x of message M previously divided into (q+1) blocks of N bits such that each enciphered block y of the message is such that:
E
(
x
)=
f
p
(
x
)⊕
K
mod
n=y,
p being greater than or equal to 4,
the device sends the (q+1) y blocks to device A
k
,
device A
k
carries out the following operation on each y:
D
(
y
)=
g
p
(
y
)⊕
K
mod
n=x,
to decipher block
y,
in order to decipher y and obtain x, the function g being the inverse function of f such that:
g
(
y
)=(
y*K
−1
mod
n
)⊕
K,
y representing a block of N bits of the cipher.
The power p indicates that functions f and g are composed p times as follows: f
p
(x)=f(f(f f(x)) )). Hence, function f is applied iteratively. The proposed number of iterations guarantees better security of the protocol. Practically speaking, hashing the message consists for example of carrying out the following steps:
E
(
x
i
)=
f
4
(
x
i
)⊕
K
mod
n
(1) The cipher y
1
of the first block x
1
of the message is calculated: y
1
=E(x
1
)
(2) For the remainder of the x
i
blocks of the message, the following calculation is performed:
y
i
=E(x
i
⊕y
i−1
)⊕y
i−1
and the last block is taken as the hashed value of the message.
According to another embodiment, when devices A
j
and A
k
communicate with each other, device A
j
first divides the message into q+1 blocks of N bits and places the blocks in two registers. One block x
i
of one message is placed in a first register and the next block x
i+1
is placed in the second register. When device A
j
sends a message, it enciphers this message with a cipher function f such that:
E
(
x
i
,x
i+1
)=
f
p
(
x
i
, x
i+1
)
with f(x
i
, x
i+1
)=y
i
, y
i+1
where y
i
=x
i+1
y
i+1
=x
i
⊕((y
i
⊕K
2
)* K
1
mod n)
The device sends the (q+1) y blocks to device A
k
.
Device A
k
performs the following operation on each block y
i
:
D
(
y
i
,y
i+1
)=
g
p
(
y
i
, y
i+1
)
so as to decipher (y
i
, y
i+1
) and obtain (x
i
, x
i+1
), the function g being the inverse function of f, this function being defined by:
g
(
y
i
,y
i+1
)=
x
i
,x
i+1
where X
i+1
=y
i
and
x
i
=y
i+1
⊕((x
i+1
⊕K
2
)* K
1
mod n)=y
i+1
⊕((y
i
⊕K
2
)* K
1
mod n)
device A
k
thus reconstituting the message.
The re
M'Raihi David
Naccache David
Gemplus
Hayes Gail
Plottel Roland
Seal James
LandOfFree
Method for implementing a private-key communication protocol... 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 implementing a private-key communication protocol..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing a private-key communication protocol... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445489