Image analysis – Pattern recognition – Unconstrained handwriting
Reexamination Certificate
1999-01-13
2001-10-02
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Unconstrained handwriting
C380S277000, C380S044000, C380S045000, C380S030000
Reexamination Certificate
active
06298153
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a digital signature method using a public key cryptogram, and an information communication system and apparatus using such a method.
2. Related Background Art
With developments and wide spreads of computers and communication networks, various functions such as social activities heretofore impossible on communication networks can be realized.
In some cases, however, it is easy for a third party to know a person, time, place, and contents during communications.
In order to prevent this, methods have been proposed which perform anonymous communications to protect privacy and realize various functions on communication networks.
For example, there is a method using a public key cryptogram. With this method, a sender can transmit communication contents only to a receiver the sender wishes to communicate, and the receiver can reliably confirm who is the sender of the received communication contents.
This method is applied to the digital signature method and an information communication system using this method disclosed in Japanese Patent Application Laid-open No. 9-108225.
“Cryptograph” and “Anonymous public key certificate” will be specifically described.
(1) “Cryptograph”
“Cryptograph” pertains information conversion in order for a third party not to recognize the meaning of information. In this cryptograph, an original text (still not converted) is called a “plain text”, converting a plain text into a text (enciphered text) the third party cannot know the meaning thereof is called “encipher”, and the conversion procedure is called a “cryptogram algorithm”.
The plain text and enciphered text are not limited only to text data, but they may be any type of data such as voices and images.
Enciphering is a conversion dependent upon parameters called “enciphering keys”. To restore the original plain text from the enciphered text is called “decipher”. In deciphering an enciphered text, a parameter called a “deciphering key” corresponding to the enciphering key is used. To restore the original plain text from the enciphered text by a third party or to find a deciphering key is called “interpret”.
Security of ciphers in such cryptograph depends on enciphering keys used for enciphering or deciphering keys used for deciphering. If it is impossible to know such a key, the plain text cannot be restored even if the cryptogram algorithm is known.
Therefore, cryptograph impossible to interpret even by a manufacture of an apparatus (cryptographic apparatus) for executing a predetermined cryptograph can be realized.
There are many cryptogram algorithms for a cryptosystem. For example, from the viewpoint of whether the enciphering key can be made public or not, the cryptography will be described by classifying it into an asymmetric cryptogram (public key cryptogram) and a symmetric cryptogram (common key cryptogram).
(1-1) “Asymmetric cryptogram (public key cryptogram)”
The “asymmetric cryptogram” is also called a “public key cryptogram”. An enciphering key is different from a deciphering key, and the deciphering key is not easy to calculate from the enciphering key. The enciphering key is made public, and the deciphering key is kept in secret.
Such an asymmetric cryptogram has the following features:
Feature 1: Since the enciphering key is different from the deciphering key and the enciphering key is made public, it is not necessary to send the enciphering key in secret.
Feature 2: Since the enciphering key of each user is made public, each user is required only to have its deciphering key in secret.
Feature 3: A certification (digital signature) function can be realized in order for a receiver to confirm that the sender of a communication text is not a pretender and that the communication text was not altered.
As the asymmetric cryptogram capable of realizing a cryptograph function and the certification function, an RST cryptosystem and an ElGamal cryptosystem are known.
As the asymmetric cryptogram capable of realizing the certification function, a Fiat-Shamir cryptosystem and a Schnorr cryptosystem are known.
Enciphering, deciphering, generation of a certificate (digital signature), and verification of the certificate regarding, for example, to the ElGamal cryptosystem will be described specifically.
It is assumed that “Z” is a set of all integers, “Z
p
” is a set of integers of 0 or larger and smaller than p, “Z
p
\{0}” is a set Z
p
without 0, and “Z
p
*” is a set of integers prime to an element of Z
p
and p.
If integers A, B, and C satisfy the following relation
A=B mod C,
then it means that the remainder of B divided by C is A (that a relation of “B=k·C+A” is satisfied where k is an arbitrary integer).
If the integers A, B, and C satisfy the following relation
A≡B (mod C),
then it means that the remainder of A divided by C is equal to the remainder of B divided by C.
Used as the public parameters shared by each communication partner are a prime p, &agr; which is an element of Z
p
* and an order p−1, and a one way hash function H
0
:Z→Z
p
\{0}. A deciphering key (secret key) of an arbitrary user i is represented by “s
i
&egr; Z
p−1
” and an enciphering key (public key) is represented by “v
i
=&agr;
si
mod p”.
The “one way hash function” is a compression function hard to generate collision. Namely, the “one way hash function” is a function of outputting a bit train having a desired length and is difficult to calculate an input which obtains the same output.
(a) Enciphering
When a user j enciphers a plain text (message) m (&egr; Z
p
) and transmits it to a user i, a user j terminal device executes the sequence from the following Step 1 to Step 4.
If the message m is not made of elements of Z
p
, i.e., if the message is made of elements larger than p, the message m is divided into blocks each being made of elements of Z
p
. Each block is enciphered by the following sequence.
Step 1: The user j terminal device generates a random number k.
Step 2: The user j terminal device calculates C
1
=&agr;
k
mod p.
Step 3: The user j terminal device calculates C
2
=m·v
i
k
mod p.
Step 4: The user j terminal device transmits the calculation results C
1
and C
2
at Steps 2 and 3 to the user i terminal device.
(b) Deciphering
With the above enciphering (a), the user j terminal device transmits C
1
and C
2
to the user i terminal device. By using C
1
and C
2
transmitted from the user j terminal device, the user j terminal device recovers the message m by calculating m=C
2
/C
1
si
mod p.
(c) Generation of Digital Signature
In generating a digital signature of the message m (&egr; Z), the user i terminal device executes the sequence from the following Step 1 to Step 4.
Although the message m is divided into blocks in some case as described in the enciphering (a), in the following example, the one way hash function is used.
Step 1: The user i terminal device generates a random number k (&egr; Z
p−1
*).
Step 2: The user i terminal device calculates
r=&agr;
k
mod p.
Step 3: The user i terminal device calculates
s=(H
0
(m)−s
i
·r)·k
−1
mod (p−1).
Step 4: The user i terminal device transmits the calculation results r and s at Steps 2 and 3 to a verifier.
(d) Verification of Digital Signature
In verifying the digital signature generated by the generation of digital signature (c), the user i terminal device checks whether the following relation is satisfied:
&agr;
H0(m)
≡v
i
r
·r
s
(mod p).
(1-2) “Symmetric cryptogram (common key cryptogram)”
The “symmetric cryptogram” is also called a “common key cryptogram”. An enciphering key is the same as a deciphering key. After the advent of the above-described asymmetric cryptogram (public key cryptogram) during the last half of 1970's, the symmetric cryptogram was also called a “conventional cryptogram”.
Such a symmetric cryptogram is classified into a block cryptogram in which each character string (block) having an appropriate
Azarian Seyed
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Johns Andrew W.
LandOfFree
Digital signature method and information communication... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital signature method and information communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital signature method and information communication... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2554689