Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-07-30
2002-11-12
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06480869
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a random-number generating circuit and more particularly a random-number generating circuit used in non-contact IC cards and reader/writers for the non-contact IC cards.
2. Description of the Related Art
Of recent years, there have been provided a number of thin non-contact IC cards that have intelligent functions, rewritable memory functions and others. Non-contact IC cards are characterized by the fact that they are able to transmit data to and from a reader/writer without being physically connected to it. Non-contact IC cards are used, for example, as prepaid cards, door keys, commutation tickets for trains and buses, tickets for ski lifts, and the like.
In order to prevent illegal retrieval or modification of data stored in a non-contact IC card, the non-contact IC card and a reader/writer of the IC card perform processing of certifying each other before transmitting data between them. The reader/writer performs the mutual authentication processing for the IC card that sends back a predetermined response signal corresponding to a polling signal that has been sent by the reader/writer. As a method of the mutual authentication processing, a method of using cryptographic keys are known.
Mutual authentication processing using cryptography between a non-contact IC card and a reader/writer is described in the following. First, the reader/writer transmits a random number a generated therein to the non-contact IC card. The non-contact IC card converts the received random number a into a random number A, using its own cryptographic key, and sends the random number A back to the reader/writer. Using a cryptographic key shared with particular non-contact IC cards, the reader/writer processes the generated random number a to obtain a random number A′ and compares the obtained random number A′ with the returned random number A. If the random numbers A and A′ coincide, the reader/writer certifies that the non-contact IC card is valid.
Next, the non-contact IC card transmits the random number b generated therein to the reader/writer. In this case, the reader/writer converts the received random number b to a random number B, using its own cryptographic key, and sends the random number B back to the non-contact IC card. Using a cryptographic key shared with particular reader/writers, the non-contact IC card processes the generated random number b to obtain a random number B′ and compares the obtained random number B′ with the returned random number B. If the random numbers B and B′ coincide, the reader/writer certifies that the reader/writer is valid.
A random-number generating circuit is built into the non-contact IC card and the reader/writer.
FIG. 10
is a circuit diagram of a random-number generating circuit
500
used in prior art. The random-number generating circuit
500
is a so-called 48-bit M-sequence random-number generating circuit. It comprises a 1-bit shift register
501
, a 2-bit shift register
504
, a 25-bit shift register
505
, and a 20-bit shift register
506
that are cascaded (in tandem) together, and adders
507
,
508
, and
509
that constitute an addition circuit that inputs the sum of the outputs of the shift registers to the input terminal of the 20-bit shift register
506
, which is on the first level.
The 1-bit shift register
501
comprises a flip-flop
502
and a transfer gate
503
that operate in synchronization with a clock signal CLK that is output from a clock circuit
510
. When address
02
E
2
H is selected by a CPU, which is not illustrated, and an address-signal line is switched from LOW to HIGH, the 1-bit shift register
501
outputs the output of the flip-flop
502
as random-number data D
1
0
.
The circuits of the 2-bit shift register
504
, 25 bit shift register
505
, and 20-bit shift register
506
are composed by connecting, in serial, a number of circuits that are the same as the 1-bit shift register
501
, with the number being the number of shifts in each shift register. The 2-bit shift register
504
outputs random-number data D
1
1
, D
1
2
, when address
15
F
2
H is selected. The 25-bit shift register
505
outputs random-number data D
1
3
-D
1
7
, D
1
8
-D
1
15
, D
2
0
-D
2
7
, and D
2
8
-D
2
11
, when addresses
15
F
2
H,
15
F
3
H,
15
F
4
H, and
15
F
5
H are selected. The 20-bit shift register
506
outputs random-number data D
2
12
-D
2
15
, D
3
0
-D
3
7
, and D
3
8
-D
3
15
, when addresses
15
F
5
H,
15
F
6
H, and
15
F
7
H are selected.
Random numbers generated by the random-number generating circuit
500
described above have a generation pattern that is repeated with a predetermined period. Therefore, communication data transmitted between the reader/writer and the non-contact IC card can be tapped, and the generation pattern of random numbers can be identified. If the generation pattern of random numbers is identified, then even if the cryptographic key and the contents of the cryptographic processing are unknown, non-contact IC cards can be forged by using a table that associates the random number a with the random number A. Similarly, the reader writer can be forged by using a table that associates the random number b with the random number B.
In order to effectively prevent the forgery of the non-contact IC card and the reader/writer through the tapping of the communication data, there is required a random-number generating circuit such that the generation pattern can not be deciphered even if the communication data is tapped. However, if the random-number generating circuit is made complicated, then illegal decipherment of the generation pattern can be effectively prevented, but the circuit size becomes large. Particularly, the size of the built-in random-number generating circuit in non-contact IC cards is preferred to be smaller.
Further, the communication processing for a non-contact IC card is required to be completed during the time when the non-contact IC card is within the area where communication with the reader/writer is possible. Therefore, communication processing including the mutual authentication processing for a non-contact IC card is required to be processed faster than for an IC card that is used by inserting to a slot.
Also, in the case of non-contact IC cards, a plurality of non-contact IC cards may simultaneously exist within an area where communication with the reader/writer is possible. In this case, before communication processing including the mutual authentication processing, each non-contact IC card is required to perform some processing for avoiding its response signal crashing against the response signal issued from other non-contact IC cards. For example, each non-contact IC card outputs its response signal to the polling signal from the reader writer, with timing based on a random number that is generated within the non-contact IC card. To improve the speed of communication between the non-contact IC card and the reader/writer, a random-number generating circuit that operates at great speed is required.
SUMMARY OF THE INVENTION
The objects of the present invention are to contribute to miniaturization of the apparatus with a built-in random-number generating circuit with a simple configuration and to provide a random-number generating circuit that generates random-number data that has no regular pattern and is hard to predict, a non-contact IC card having the random-number generating circuit built therein, and a reader/writer for non-contact IC cards having the random-number generating circuit built therein.
The random-number generating circuit in a first embodiment in accordance with the present invention comprises a plurality of shift registers synchronized with a clock and cascaded together, a circuit that obtains the sum of the outputs of more than one of the shift registers and inputs the obtained sum to the input terminal of the shift register on the first stage, and a clock generating circuit that inputs a clock signal to each of the shift registers. The random-nu
Malzahn David H.
McDermott & Will & Emery
Mitsubishi Denki & Kabushiki Kaisha
LandOfFree
Random-number generating circuit, non-contact IC card having... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random-number generating circuit, non-contact IC card having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random-number generating circuit, non-contact IC card having... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2916599