Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-07-26
2004-01-27
Morse, Gregory (Department: 2134)
Cryptography
Particular algorithmic function encoding
C380S059000
Reexamination Certificate
active
06683953
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an encryption method for converting plain text to cipher (or encrypted) text, and a code -communications system using that method.
2. Description of the Related Art
In our modern society, which is called a high-level information society, important business textual and graphic information is exchanged in communications and processed as electronic information through computer network infrastructure. One characteristic of such electronic information is that it can easily be duplicated, whereupon it becomes very difficult to distinguish the duplicate from the original. Hence the problem of information security is seen to be critical. This is especially true in view of the fact that the implementation of computer networks that support features such as “computer resource sharing,” “multi-access,” and “wide area operations” is indispensable to the realization of the high-level information society, but these features involve aspects that are inconsistent with the protection of information exchanged between authorized participants. In this context, attention is now being drawn to coding technologies that in the past have been employed primarily in military and diplomatic communications.
Coding is exchanging of information in such a way that its meaning cannot be understood by anyone other than the authorized parties. In coding operations, the conversion of the original text (plain text) that anyone can understand to text (cipher text) the meaning of which cannot be understood by a third party is called encryption, and the restoration of that cipher text to plain text is called decryption. The overall system wherein this encryption and decryption is performed is called a cryptosystem. In the processes of encryption and decryption, respectively, secret information called encryption keys and decryption keys are employed. A secret decryption key is necessary at the time of decryption, wherefore only a party knowledgeable of that decryption key can decrypt the cipher text. The confidentiality of the information is accordingly maintained by the encryption.
Cryptosystems can be subsumed under two broad categories, namely common key cryptosystems and public key cryptosystems. In a common key cryptosystem, the encryption key and the decryption key are identical, and coded communications are conducted by having both the sending party and receiving party hold the same key. The sending party encrypts plain text based on the common secret key and send it to the receiving party, whereupon the receiving party uses the same key to decrypt the cipher text and restore it to the original plain text.
In contrast thereto, in a public key cryptosystem, the encryption key and decryption key are different. In conducting coded communications in this cryptosystem, the sending party encrypts the plain text with the public key derived from a receiving party, and the receiving party decrypts that cipher text with his or her own secret key. The public key is used for encryption, and the secret key is a key for decrypting the cipher text converted by the public key. The cipher text converted by the public key can only be decrypted using a secret key.
One example of such a public key cryptosystem is seen in the conventional knapsack coding schemes wherein safety is based on the knapsack problem. However, almost all of the knapsack coding schemes now being proposed exhibit either linearity or super-increasing, wherefore it has been demonstrated that they can be decrypted using the Shamir attack method and Lenstra-Lenstra-Lovasz (LLL) algorithms. To overcome this shortcoming, multiplication knapsack coding schemes have been developed which employ power operation over modulo-calculation, an example whereof is seen in the Morii-Kasahara cryptosystem (Masakatsu Morii and Masao Kasahara: “Denshi Joho Tsushin Gakkai [Electronic Information Communications Society],” Vol. j71-D, No. 2 (1988)). This Morii-Kasahara cryptosystem (hereinafter referred to as the MK cryptosystem) is now described.
In this description, the following three definitions are given.
(Divisibility Discriminator Symbol)
A divisibility discriminator symbol < > for determining whether or not b is evenly divisible by a is defined below.
⟨
b
a
⟩
=
def
{
0
(
when
b
is
not
evenly
divisible
by
a
)
1
(
when
b
is
evenly
divisible
by
a
)
(Scalar exponentiation)
C=A
e
If A and C are vectors and e is a scalar, then scalar exponentiation is defined as follows.
(Scalar exponentiation)
C=A
e
c
ij
=a
e
ij
(Matrix right exponentiation)
C=A
B
If A, B, and C are vectors, then right exponentiation of matrix is defined as follows.
(
matrix
right
exponentiation
)
C
=
A
B
c
ij
=
∏
k
a
ik
b
kj
(Key Generation)
In the MK cryptosystem, the secret and public keys are generated as follows.
Secret key
secret vector a
vector a =
t
(a
1
, a
2
, . . . , a
n
)
gcd (a
i
, a
j
) = 1 (i ≠ j)
encryption key e
gcd (e, p
MK
− 1) = 1
decryption key d
ed = 1 (mod p
MK
− 1)
Public key
modulus (prime) p
MK
to satisfy Condition 1 below
public vector c
vector c = vector a
e
(mod p
MK
)
Condition 1:
p
MK
>
∏
i
=
1
n
a
i
(
1
)
(Encryption)
Treating the plain text as the vector x=
t
(x
1
, x
2
, . . . , x
n
), the sending party creates the cipher text C by the following equation and sends it to the receiving party.
C
=
c
x
t
=
∏
i
=
1
n
c
i
xi
(
mod
p
MK
)
(Decryption)
The receiving party, using the following equation, raises the received cipher text C to the power of d and converts it to A.
A=C
d
=(
t
c
x
)
d
=
t
a
edx
=
t
a
x
(mod
p
MK
)
Then, as represented in the following equation, divisibility determination is performed on A using the components of the secret vector a, whereby decryption can be done to obtain the original plain text vector.
x
=
t
(
⟨
A
a
1
⟩
,
⟨
A
a
2
⟩
,
…
,
⟨
A
a
n
⟩
)
Specific examples involving this MK cryptosystem are described next.
(Key Generation)
Secret key
vector a=
t
(13, 9, 25, 16, 7, 17)
e=1501, d=11131
Public key
p
MK
=5569211 to satisfy Condition 2 below
vector
c
=
vector
a
ⅇ
=
t
(
13
1501
,
9
1501
,
25
1501
,
16
1501
,
7
1501
,
17
1501
)
=
t
(
5097951
,
4832634
,
2171018
,
2905496
,
1517072
,
319194
)
(
mod
5569211
)
Condition 2:
p
MK
=5569211>Π
i=1
6
a
i
=5569200 (2)
(Encryption)
Encryption is performed, treating the plain text as the vector
x
=
t
(
1
,
0
,
1
,
1
,
1
,
0
)
.
C
=
5097951
·
2171018
·
2905496
·
1517072
=
5328558
(
mod
5569211
)
(Decryption)
After raising the cipher text C to the power of d to obtain A, the original plain text vector x is obtained by performing divisibility determination on A using the components of the secret vector a, as in Equation 3 below.
A=C
d
=5328558
11131
=36400(mod 5569211)
x
=
t
(
⟨
36400
13
⟩
,
⟨
36400
9
⟩
,
⟨
36400
25
⟩
,
⟨
36400
16
⟩
,
⟨
36400
7
⟩
⟨
36400
17
⟩
)
=
&thinsp
Kasahara Masao
Kiuchi Shinya
Murakami Yasuyuki
Brown Christopher J.
Hogan & Hartson LLP
Kasahara Masao
Morse Gregory
LandOfFree
Encoding method, encoding-decoding apparatus, and code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encoding method, encoding-decoding apparatus, and code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding method, encoding-decoding apparatus, and code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3256987