EP0933695A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
IC card equipped with elliptic curve encryption processing facility
Assignee: Hitachi Ltd
•
Filing: 1999-01-26
•
Granted: —
•
Expires: 2019-01-26
Abstract
Abstract Residual arithmetic succeeding to generation of a random number and residual arithmetic in a signature generating processing can be executed by using a residual multiplier (109). Further, in order to use effectively the residual multiplier (109) for arithmetic operation on an elliptic curve, the point on the elliptic curve is transformed from a two-dimensional affine coordinate system to a three-dimensional coordinate system. Additionally, multiplicative inverse arithmetic for realizing reverse transformation from the three-dimensional coordinate system to the two-dimensional affine coordinate system as well as for determining a signature s can be executed only with the residual multiplication arithmetic. By making use of the residual multiplier (109) in this manner, the processing speed can be increased. Computation complexity can be reduced by storing previously those parameters which are used frequently and constant multiplies of a base point of the elliptic curve in the form of tables, which also contributes to increasing of processing speed.
Inventors
- 👤 Seiji Miyazaki
- 👤 Kazuo Takaragi
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-27 18:58
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725; G06F7/728
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
181 words
An IC card, comprising: message receiving means for receiving a message
(M) from an input/output terminal (114) by way of an
input/output port; public key encryption processing means (102-104;
106-109) for performing elliptic curve encryption
processing on said message (M); and output means for outputting result of the
processing executed by said public key encryption
processing means from the input/output terminal (114) via
the input/output port (105), wherein said public key encryption processing
means comprises: multiple length arithmetic means for
calculating through multiple length residual
multiplication arithmetic values "ABR -1 mod N", "A 2 R -1 mod
N", and "AR -1 mod N" representing, respectively,
numerical values to undergo computation which make
appearance in intermediate arithmetic processing for
positive integers A, B, N and R, wherein A and B
represent, respectively, variables which are given by
input variables and/or interim variables, N represents a
variable given as an input variable, and R represents a
numerical value given as a constant; and computation means for performing multiplication
and multiplicative inverse arithmetic on a finite group
by using said multiple length arithmetic means.
Claim 2
Dependent Claim
34 words
An IC card according to claim 1, wherein said multiple length arithmetic means
is constituted by a co-processor, and wherein said variable R represents a constant
determined in dependence on performance of said co-processor.
Claim 3
Dependent Claim
57 words
An IC card according to claim 1, wherein said computation means includes
multiplicative inverse arithmetic means for performing
arithmetic operation represented by "k -1 mod n" for a
positive integer k which is relatively prime n by
resorting to residual multiplication arithmetic
represented by "k (n-2) mod n" with the aid of said multiple
length arithmetic means.
Claim 4
Dependent Claim
135 words
An IC card according to claim 1, wherein said
public key encryption processing is an elliptic curve
encryption processing, further comprising: a rewritable nonvolatile memory (104) for
storing previously at least one of numerical values given
by "2R mod p", "3R mod p", "4R mod p", "8R mod p", "2 -1 R
mod p", "aR mod p", "R mod p", "R 2 mod p", "R mod n", and
"R 2 mod n", respectively, where R represents a positive
integer which satisfies a condition that R > p, R > n for
order (p) of a finite field when an elliptic curve (Ep)
on the finite field is given by "y 2 ≡ x 3 + ax + b (mod
p)", wherein said rewritable nonvolatile memory
(104) can be referenced by said multiple length
arithmetic means.
Claim 5
Dependent Claim
60 words
An IC card according to claim 1, further comprising: a rewritable nonvolatile memory (104) for
storing previously values of points corresponding to
positive integer multiplies of a base point (P) on said
elliptic curve, wherein said values of the points corresponding
to the positive integer multiplies of the base point (P)
can be referenced by said multiple length arithmetic
means.
Claim 6
Dependent Claim
174 words
An encryption processing method for an IC card
having a co-processor, comprising the steps of: receiving a message (M) from an input/output
terminal (114) by way of an input/output port (105); performing elliptic curve encryption processing
on said message (M); and outputting result of the processing executed in
said elliptic curve encryption processing step from the
input/output terminal (114) via the input/output port
(105), wherein said elliptic curve encryption
processing step comprises the steps of: calculating through multiple length residual
multiplication arithmetic by using said co-processor
values "ABR -1 mod N", "A 2 R -1 mod N", and "AR -1 mod N"
representing, respectively, numerical values to undergo
computation which make appearance in intermediate
arithmetic processing for positive integers A, B, N and
R, wherein A and B represent, respectively, variables
which are given as input variables and/or interim
variables, N represents a variable given as an input
variable, and R represents a numerical value given as a
constant; and executing multiplication and multiplicative
inverse arithmetic on a finite group by using said co-processor.
Claim 7
Dependent Claim
63 words
An encryption processing method according to
claim 6, wherein said computation step includes a
substep of executing a multiplicative inverse arithmetic
for performing arithmetic operation represented by "k -1 mod n" for a positive integer k which is relatively prime
to a prime number n by resorting to residual
multiplication arithmetic represented by "k (n-2) mod n"
with the aid of said co-processor.
Claim 8
Dependent Claim
182 words
A program stored in a recording medium for
performing encryption processing for an IC card having a
co-processor, comprising the instruction steps of: receiving a message (M) from an input/output
terminal (114) by way of an input/output port (105); performing elliptic curve encryption processing
on said message (M); and outputting result of the processing executed in
said elliptic curve encryption processing step from the
input/output terminal (114) via the input/output port
(105), wherein said elliptic curve encryption
processing step comprises the substeps of: calculating through multiple length residual
multiplication arithmetic by using said co-processor
values "ABR -1 mod N", "A 2 R -1 mod N", and "AR -1 mod N"
representing, respectively, numerical values to undergo
computation which make appearance in intermediate
arithmetic processing for positive integers A, B, N and
R, wherein A and B represent, respectively, variables
which are given as input variables and/or interim
variables, N represents a variable given as an input
variable, and R represents a numerical value given as a
constant; and executing multiplication and multiplicative
inverse arithmetic on a finite group by using said co-processor.
Claim 9
Dependent Claim
186 words
A multiplicative inverse arithmetic module
destined for use in an electronic device incorporating an
encryption processing unit including a residual
multiplier, for performing at high-speed arithmetic
operation given by "k -1 mod n" on a positive integer k which is to be generated and which is relatively prime to
a prime number n in an encryption processing by using
said residual multiplier having performance by which a
constant (R) is determined, comprising: first means for calculating "kR mod n" with
said residual multiplier, result of said calculation
being set equally in a first register (CDA) and a second
register (CDB), second means for squaring and multiplying by
R -1 the value of said first register, result of which is
stored in said first register to modulus n ; third means for multiplying the values of said
first register and said second register and then
multiplying the multiplied value by R -1 , result of which
is stored in said first register to modulus n ; and fourth means for determining "k (n-2) mod n" by
repeating processings executed by said first means and
said second means.
Claim 10
Dependent Claim
18 words
A multiplicative inverse arithmetic module
according to claim 9, wherein said residual multiplier is constituted
by a co-processor.
Claim 11
Dependent Claim
13 words
A semiconductor chip according to claim 10,
comprising: a multiplicative inverse arithmetic module.
Claim 12
Dependent Claim
26 words
An IC card including an encryption processing
unit according to claim 11, wherein said IC card includes a semiconductor
chip packaging a multiplicative inverse arithmetic
module.
Claim 13
Dependent Claim
119 words
An IC device for generating digital signature
by resorting to an elliptic curve encryption, comprising: first means for generating a random number to
modulus n , where n represents order, second means for scalar multiplication or
addition arithmetic for calculating a point corresponding
to a known point on an elliptic curve multiplied with k by means of a residual multiplier; and third means for determining a value " r = x mod
n " with point k·P on the elliptic curve being inputted
and then determining a value s by using the determined
value r with the aid of said residual multiplier, said
values r and s constituting parts of a digital signature,
to thereby generate a digital signature.
Claim 14
Dependent Claim
16 words
An IC device according to claim 13, wherein said residual multiplier is constituted
by a co-processor.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.