Scheme for fast realization of encryption, decryption and authentication

Claim 2

The method of claim 1, wherein the setting step sets three prime numbers p 1 = p, p 2 = q and p 3 = r as the first secret key and a product p k q ℓ r m where k = k1, ℓ = k2 and m = k3 as the first public key n.

Claim 3

The method of claim 1, wherein the setting step sets two prime numbers p 1 = p and p 2 = q as the first secret key and a product p k q where k = k1 as the first public key n.

Claim 4

The method of claim 3, wherein the determining step also determines: d p := d (mod p-1), and d q := d (mod q-1), as the second secret key such that the second secret key is given by a set of d, d p and d q .

Claim 5

A decryption method for decrypting a ciphertext C obtained from a plaintext M according to: C ≡ M e (mod n) using a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, the method comprising the steps of: obtaining residues M p 1 k 1 , M p 2 k 2 , ········ , M p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N ; and recovering the plaintext M by applying Chinese remainder theorem to the residues M p 1 k 1 , M p 2 k 2 , ········ , M p N k N .

Claim 6

The method of claim 5, wherein the ciphertext C is obtained using the first secret key given by three prime numbers p 1 = p, p 2 = q and p 3 = r and the first public key n given by a product p k q ℓ r m where k = k1, ℓ = k2 and m = k3 ; the obtaining step obtains K ⊘ p , K ⊘ q and K ⊘ r modulo p, q and r, respectively, by integer modular exponent calculations of: K ⊘ p := C d p (mod p); K ⊘ q := C d q (mod q); and K ⊘ r := C d r (mod r); where: dp := d (mod p-1); dq := d (mod q-1); and dr := d (mod r-1); and then obtaining the residues M p k , M q ℓ and M r m modulo p k , q ℓ and r m , respectively, by applying the prescribed loop calculation to K ⊘ p , K ⊘ q and K ⊘ r , respectively; and the recovering step applies the Chinese remainder theorem to the residues M p k , M q ℓ and M r m .

Claim 7

The method of claim 5, wherein the ciphertext C is obtained using the first secret key given by two prime numbers p 1 = p and p 2 = q and the first public key n given by a product p k q where k = k1; the obtaining step obtains a residue K ⊘ modulo p and a residue M q modulo q of the plaintext M, by integer modular exponent calculations of: K ⊘ := C d p (mod p); and M q ;= C d p (mod q); where: dp := d (mod p-1); and dq := d (mod q-1); and obtains a residue M p k modulo p k of the plaintext M by applying the prescribed loop calculation to K ⊘ ; and the recovering steps applies the Chinese remainder theorem to the residues M p k and M q .

Claim 8

The method of claim 7, wherein the prescribed loop calculation is carried out by: (a) setting A ⊘ := K ⊘ ; (b) for i = 1 to (k-1), repeatedly calculating: (c) setting M p k := A k-1 .

Claim 9

The method of claim 7, wherein the recovering step recovers the plaintext M by calculating: q 1 := q - 1 (mod p k) ; v 1 := ((M p k - M q )q 1 ) (mod p k ); and M := (M q + qv 1 ).

Claim 10

The method of claim 7, wherein the recovering step recovers the plaintext M by calculating: p 1 := (p k ) -1 (mod q); v 1 := ((M q - M p k )p 1 ) (mod q); and M := (M p k + p k v 1 ).

Claim 11

The method of claim 7, wherein the recovering step recovers the plaintext M by calculating: p 1 := (p k ) - 1 (mod q); q 1 := q - 1 (mod p k ); and M := (q 1 qM p k + p 1 p k M q ) (mod p k q).

Claim 12

An authentication method for authenticating an authentication message sent from a sender to a receiver, comprising the steps of: (a) setting at the sender side a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1; (b) obtaining at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; (c) obtaining at the sender side an encrypted authenticator h(C) of the authenticator h(M) according to: h(M) ≡ h(C) e (mod n) by obtaining residues h(C) p 1 k 1 , h(C) p 2 k 2 , ········ , h(C) p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the encrypted authenticator h(C) using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N , and applying Chinese remainder theorem to the residues h(C) p 1 k 1 , h(C) p 2 k 2 , ········ , h(C) p N k N ; (d) sending the encrypted authenticator h(C) and the authentication message M from the sender to the receiver; (e) obtaining at the receiver side a first authenticator h(M) 1 by calculating h(C) e (mod n) from the encrypted authenticator h(C) received from the sender using the second public key e; (f) obtaining at the receiver side a second authenticator h(M) 2 by hashing the authentication message M received from the sender using the hash function h; and (g) judging an authenticity of the authentication message M at the receiver side by checking whether the first authenticator h(M) 1 and the second authenticator h(M) 2 coincide or not.

Claim 13

The method of claim 12, wherein the encrypted authenticator h(C) is obtained using the first secret key given by three prime numbers p 1 = p, p 2 = q and p 3 = r and the first public key n given by a product p k q ℓ r m where k = k1, ℓ = k2 and m = k3 ; the step (c) obtains h(K) ⊘ p , h(K) ⊘ q and h(K) ⊘ r modulo p, q and r, respectively, by integer modular exponent calculations of: h(K) ⊘ p := h(M) d p (mod p); h(K) ⊘ q := h(M) d q (mod q); and h(K) ⊘ r := h(M) d r (mod r); where: dp := d (mod p-1); dq := d (mod q-1); and dr := d (mod r-1); and then obtaining the residues h(C) p k , h(C) q ℓ and h(C) r m modulo p k , q ℓ and r m , respectively, by applying the prescribed loop calculation to h(K) ⊘ p , h(K) ⊘ q and h(K) ⊘ r , respectively, and applies the Chinese remainder theorem to the residues h(C) p k , h(C) q ℓ and h(C) r m .

Claim 14

The method of claim 12, wherein the encrypted authenticator h(C) is obtained using the first secret key given by two prime numbers p 1 = p and p 2 = q and the first public key n given by a product p k q where k = k1; the step (c) obtains a residue h(K) ⊘ modulo p and a residue h(C) q modulo q of the encrypted authenticator h(C), by integer modular exponent calculations of: h(K) ⊘ := h(M) d p (mod p); and h(C) q := h(M) d q (mod q); where: dp := d (mod p-1); and dq := d (mod q-1); and obtains a residue h(C) p k modulo p k of the encrypted authenticator h(C) by applying the prescribed loop calculation to h(K) ⊘ , and applies the Chinese remainder theorem to the residues h(C) p k and h(C) q .

Claim 15

The method of claim 14, wherein the prescribed loop calculation is carried out by: (a) setting h(A) ⊘ := h(K) ⊘ ; (b) for i = 1 to (k-1), repeatedly calculating: (c) setting h(C) p k := h(A) k - 1 .

Claim 16

The method of claim 14, wherein the step (c) applies the Chinese remainder theorem by calculating: q 1 := q - 1 (mod p k ); v 1 := ((h(C) p k - h(C) q )q 1 ) (mod p k ); and h(C) := (h(C) q + qv 1 ).

Claim 17

The method of claim 14, wherein the step (c) applies the Chinese remainder theorem by calculating: p 1 := (p k ) - 1 (mod q); v 1 := ((h(C) q - h(C) p k )p 1 ) (mod q); and h(C) := (h(C) p k + p k v 1 ).

Claim 18

The method of claim 14, wherein the step (c) applies the Chinese remainder theorem by calculating: p 1 := (p k ) - 1 (mod q); q 1 := q - 1 (mod p k ); and h(C) := (q 1 qh(C) p k + p 1 p k h(C) q ) (mod p k q).

Claim 19

An encryption apparatus, comprising: an encryption/decryption key generation processing unit for setting N (≧ 2) prime numbers p 1 , p 2 , ········ , p N as a first secret key, and a product p 1 k 1 p 2 k 2 ········ p N k N as a first public key n, where k1, k2, ········ , kN are arbitrary positive integers, and determining a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, using the first secret key; and an encryption processing unit for obtaining a ciphertext C from a plaintext M according to: C ≡ M e (mod n) using the first public key n and the second public key e.

Claim 20

A decryption apparatus for decrypting a ciphertext C obtained from a plaintext M according to: C ≡ M e (mod n) using a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, the apparatus comprising: a calculation processing unit for obtaining residues M p 1 k 1 , M p 2 k 2 , ········ , M p N k N modulo p 1 k 1 , p 2 k 2 ········ p N k N , respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N ; and a decryption processing unit for recovering the plaintext M by applying Chinese remainder theorem to the residues M p 1 k 1, M p 2 k 2, ········ , M p N k N .

Claim 21

A cipher communication system, comprising: a sender apparatus having: an encryption/decryption key generation processing unit for setting N (≧ 2) prime numbers p 1 , p 2 , ········ , p N as a first secret key, and a product p 1 k 1 p 2 k 2 ········ p N k N as a first public key n, where k1, k2, ········ , kN are arbitrary positive integers, and determining a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, using the first secret key; and an encryption processing unit for obtaining a ciphertext C from a plaintext M according to: C ≡ M e (mod n) using the first public key n and the second public key e; and a receiver apparatus having: a calculation processing unit for obtaining residues M p 1 k 1, M p 2 k 2, ········ , M p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N ; and a decryption processing unit for recovering the plaintext M by applying Chinese remainder theorem to the residues M p 1 k 1 , M p 2 k 2 , ········ , M p N k N.

Claim 22

An authentication message sender apparatus for use in authenticating an authentication message sent from a sender to a receiver, the apparatus comprising: an encryption/decryption key generation processing unit for setting at the sender side a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1; an authentication message hashing processing unit for obtaining at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; and an authenticator encryption processing unit for obtaining at the sender side an encrypted authenticator h(C) of the authenticator h(M) according to: h(M) ≡ h(C) e (mod n) by obtaining residues h(C) p 1 k 1 , h(C) p 2 k 2 , ········ , h(C) p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the encrypted authenticator h(C) using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N , and applying Chinese remainder theorem to the residues h(C) p 1 k 1 , h(C) p 2 k 2 , ········ , h(C) p N k N , and then sending the encrypted authenticator h(C) and the authentication message M to the receiver.

Claim 23

An authentication message receiver apparatus for use in authenticating an authentication message sent from a sender to a receiver, using a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, the apparatus comprising: an authenticator decryption processing unit for obtaining a first authenticator h(M) 1 by calculating h(C) e (mod n) from an encrypted authenticator h(C) received from the sender using the second public key e; an authentication message hashing processing unit for obtaining a second authenticator h(M) 2 by hashing an authentication message M received from the sender using a hash function h; and an authenticity verification processing unit for judging an authenticity of the authentication message M at the receiver side by checking whether the first authenticator h(M) 1 and the second authenticator h(M) 2 coincide or not.

Claim 24

An authentication system for authenticating an authentication message sent from a sender to a receiver, the system comprising: a sender apparatus having: an encryption/decryption key generation processing unit for setting at the sender side a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1; an authentication message hashing processing unit for obtaining at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; and an authenticator encryption processing unit for obtaining at the sender side an encrypted authenticator h(C) of the authenticator h(M) according to: h(M) ≡ h(C) e (mod n) by obtaining residues h(C) p 1 k 1 , h(C) p 2 k 2 , ········ , h(C) p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the encrypted authenticator h(C) using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ ,p N , and applying Chinese remainder theorem to the residues h(C) p 1 k 1, h(C) p 2 k 2, ········ , h(C) p N k N , and then sending the encrypted authenticator h(C) and the authentication message M to the receiver; and a receiver apparatus having: an authenticator decryption processing unit for obtaining a first authenticator h(M) 1 by calculating h(C) e (mod n) from the encrypted authenticator h(C) received from the sender using the second public key e; an authentication message hashing processing unit for obtaining a second authenticator h(M) 2 by hashing the authentication message M received from the sender using the hash function h; and an authenticity verification processing unit for judging an authenticity of the authentication message M by checking whether the first authenticator h(M) 1 and the second authenticator h(M) 2 coincide or not.

Claim 25

A computer usable medium having computer readable program code means embodied therein for causing a computer to function as an encryption apparatus, the computer readable program code means includes: first computer readable program code means for causing said computer to set N (≧ 2) prime numbers p 1 , p 2 , ········ , p N as a first secret key, and a product p 1 k 1 p 2 k 2 ········ p N k N as a first public key n, where k1, k2, ········ , kN are arbitrary positive integers, and determining a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, using the first secret key; and second computer readable program code means for causing said computer to obtain a ciphertext C from a plaintext M according to: C ≡ M e (mod n) using the first public key n and the second public key e.

Claim 26

A computer usable medium having computer readable program code means embodied therein for causing a computer to function as a decryption apparatus for decrypting a ciphertext C obtained from a plaintext M according to: C ≡ M e (mod n) using a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, the computer readable program code means includes: first computer readable program code means for causing said computer to obtain residues M p 1 k 1, M p 2 k 2, ········ , M p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N ; and second computer readable program code means for causing said computer to recover the plaintext M by applying Chinese remainder theorem to the residues M p 1 k 1 , M p 2 k 2 , ········ , M p N k N .

Claim 27

A computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message sender apparatus for use in authenticating an authentication message sent from a sender to a receiver, the computer readable program code means includes: first computer readable program code means for causing said computer to set at the sender side a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1; second computer readable program code means for causing said computer to obtain at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; and third computer readable program code means for causing said computer to obtain at the sender side an encrypted authenticator h(C) of the authenticator h(M) according to: h(M) ≡ h(C) e (mod n) by obtaining residues h(C) p 1 k 1, h(C) p 2 k 2, ········ , h(C) p N k N modulo p 1 k 1 , p 2 k 2 , ········ , p N k N , respectively, of the encrypted authenticator h(C) using a prescribed loop calculation with respect to the first secret key p 1 , p 2 , ········ , p N , and applying Chinese remainder theorem to the residues h(C) p 1 k 1, h(C) p 2 k 2, ········ , h(C) p N k N , and then sending the encrypted authenticator h(C) and the authentication message M to the receiver.

Claim 28

A computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message receiver apparatus for use in authenticating an authentication message sent from a sender to a receiver, using a first secret key given by N (≧ 2) prime numbers p 1 , p 2 , ········ , p N , a first public key n given by a product p 1 k 1 p 2 k 2 ········ p N k N where k1, k2, ········ , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy: ed ≡ 1 (mod L) where L is a least common multiple of p 1 -1, p 2 -1, ········ , p N -1, the computer readable program code means includes: first computer readable program code means for causing said computer to obtain a first authenticator h(M) 1 by calculating h(C) e (mod n) from an encrypted authenticator h(C) received from the sender using the second public key e; second computer readable program code means for causing said computer to obtain a second authenticator h(M) 2 by hashing an authentication message M received from the sender using a hash function h; and third computer readable program code means for causing said computer to judge an authenticity of the authentication message M at the receiver side by checking whether the first authenticator h(M) 1 and the second authenticator h(M) 2 coincide or not.