CRT-RSA encryption method and apparatus

1. A Chinese Remainder Theorem (CRT)-Rivest Shamir Adleman (RSA) (CRT-RSA) encryption method, comprising:

calculating, using an intermediate value calculator, a first parameter information and a second parameter information based on a secret key, respectively;

performing a modular exponential calculation process with respect to a next block based on calculation information of a previous block according to a block unit divided respectively from the first parameter information and second parameter information; and

calculating, using a CRT calculator, an encryption process result based on a CRT calculation using results of the modular exponential calculation,

wherein the modular exponential calculation process includes:

extracting N (N≧2, where N is an integer) block information from the first parameter information and the second parameter information, respectively; and

performing a plurality of modular exponential calculations based on the N block information.

2. The CRT-RSA encryption method of claim 1 , wherein the calculating of the first parameter information and the second parameter information comprises:

determining intermediate calculation information d p and d q respectively generated by equations: d p =d mod(p−1) and d q =d mod(q−1) as the first parameter information and the second parameter information, wherein d denotes the secret key, p and q denote prime numbers, and a public key N satisfies the condition (N=p times q).

3. The CRT-RSA encryption method of claim 1 , wherein the calculating of the first parameter information and the second parameter information comprises:

calculating intermediate calculation information d p and d q based on equations d p =d mod(p−1) and d q =d mod(q−1); and

calculating the first parameter information d′ p and the second parameter information d′ q by respectively deriving d′ p and d′ q from the intermediate calculation information d p and d q using both the intermediate calculation information d p and d q ,

wherein d denotes the secret key, p and q denote prime numbers, and a public key N satisfies the condition (N=p times q).

4. The CRT-RSA encryption method of claim 1 , wherein the performing of the modular exponential calculation process comprises:

dividing the first parameter information and the second parameter information respectively into N blocks.

5. The CRT-RSA encryption method of claim 4 , wherein the first parameter information and the second parameter information are respectively divided into the N blocks of equal size.

6. The CRT-RSA encryption method of claim 1 , wherein the extracting of the N block information from the first parameter information and the second parameter information, respectively, comprises:

performing a first modular exponential calculation based on a first (1A) block information;

performing a second modular exponential calculation based on a second (2A) block information;

performing a third modular exponential calculation based on a third (1B) block information using a result of the modular exponential calculation of the first (1A) block information; and

performing a fourth modular exponential calculation based on a fourth (2B) block information using a result of the modular exponential calculation of the second (2A) block information.

7. The CRT-RSA encryption method of claim 6 , wherein the extracting of the first (1A) block information comprises:

calculating the first (1A) block information L′ d p based on an equation

L

d

p

′

=

Left

⁢

⁢

B

⁡

(

d

p

′

)

=

∑

i

=

n

2

n

-

1

⁢

⁢

d

p

i

′

⁢

2

i

-

n

2

=

(

d

p

n

-

1

′

,

d

p

n

-

2

′

,

…

⁢

,

d

p

n

2

′

)

2

 from the first parameter information d′ p having an n-bit length.

8. The CRT-RSA encryption method of claim 6 , wherein the extracting of the second (2A) block information comprises:

calculating the second (2A) block information L′ d q based on an

L

d

q

′

=

Left

⁢

⁢

B

⁡

(

d

q

′

)

=

∑

i

=

n

2

n

-

1

⁢

⁢

d

q

i

′

⁢

2

i

-

n

2

=

(

d

q

n

-

1

′

,

d

q

n

-

2

′

,

…

⁢

,

d

q

n

2

′

)

2

 equation from the second parameter information d′ q having an n-bit length.

9. The CRT-RSA encryption method of claim 6 , wherein the performing of the first modular exponential calculation comprises:

calculating a first calculation value L S p and a second calculation value L′ S p that are modular exponential calculation results with respect to the first (1A) block information L′ d p divided from the first parameter information d′ p based on equations L S p =m LeftB(d′ p )+1 mod sp and L′ S p =m Left(d′ p ) mod sp, wherein m denotes a message to be encrypted, and s denotes a random number.

10. The CRT-RSA encryption method of claim 9 , wherein the performing of the first modular exponential calculation comprises:

calculating a third calculation value CK L p based on an equation CK Lp =LeftB(d′ p )⊕p′, where p′ denotes intermediate calculation information derived from a prime number p.

11. The CRT-RSA encryption method of claim 6 , wherein the performing of the second modular exponential calculation comprises:

calculating a calculation value L S q and a calculation value L′ S q that are modular exponential calculation results with respect to the second (2A) block information L′ d q divided from the second parameter information d′ q based on equations: L S q =m LeftB(d′ q )+1 mod sq and L′ S q =m LeftB(d′ q ) mod sq wherein m is a message to be encrypted, and ‘s’ denotes a random number.

12. The CRT-RSA encryption method of claim 11 , wherein the performing of the second modular exponential calculation further comprises:

calculating a calculation value CK L q based on an equation CK L q =LeftB(d′ q )⊕q′, wherein q′ denotes intermediate calculation information derived from a prime number q.

13. The CRT-RSA encryption method of claim 6 , wherein the extracting of the third (1B) block information comprises:

calculating the third (1B) block information R′ d p from the first parameter information d′ p having an n-bit length based on an equation

R

d

p

′

=

(

Ψ

d

⊕

d

q

′

)

-

t

d

p

′

·

2

n

2

,

 wherein Ψ d is determined based on d p and d q , d p and d q are determined respectively based on equations d p =d mod(p−1) and d q =d mod(q−1), t′ d p is determined based on the first (1A) block information and the intermediate calculation information, wherein d′ q denotes the second parameter information.

14. The CRT-RSA encryption method of claim 6 , wherein the extracting of the fourth (2B) block information comprises:

calculating the fourth (2B) block information R′ d q from the second parameter information d′ q of an n-bit length based on an equation

R

d

q

′

=

(

Ψ

d

⊕

d

p

′

)

-

t

d

q

′

·

2

n

2

,

 wherein Ψ d is determined based on d p and d q , d p and d q are determined respectively based on equations d p =d mod(p−1) and d q =d mod(q−1), t′ d q is determined based on the first (1A) block information and the intermediate calculation information, wherein d′ p denotes the first parameter information.

15. The CRT-RSA encryption method of claim 6 , wherein the performing of the third modular exponential calculation comprises:

calculating a calculation value R S p and a calculation value R′ s p using equations R S p =m d′ p mod sp and R′ S p =m d′ p −1 mod sp by performing a modular exponential calculation with respect to the third (1B) block information R′ d p using the modular exponential calculation result with respect to the first (1A) block information L′ d p , wherein d′ p denotes the first parameter information, m denotes a message to be encrypted, and s denotes a random number.

16. The CRT-RSA encryption method of claim 15 , wherein the performing of the third modular exponential calculation further comprises:

calculating a ninth calculation value CK R p using the equation

CK

R

p

=

(

∑

i

=

0

n

2

-

1

⁢

⁢

d

p

i

′

·

2

i

)

⊕

p

′

,

 wherein p′ denotes intermediate calculation information derived from a prime number p.

17. The CRT-RSA encryption method of claim 6 , wherein the performing of the fourth modular exponential calculation comprises:

calculating a calculation value R S q and a calculation value R′ S q using the equations R S q =m d′ q mod sq and R′ S q =m d′ q −1 mod sq by performing a modular exponential calculation with respect to the fourth (2B) block information R′ d q using the modular exponential calculation information with respect to the second (2A) block information L′ d q , wherein d′ q denotes the second parameter information, m denotes a message to be encrypted, and s denotes a random number.

18. The CRT-RSA encryption method of claim 17 , wherein the performing of the fourth modular exponential calculation further comprises:

calculating a calculation value CK R q based on an equation

CK

R

q

=

(

∑

i

=

0

n

2

-

1

⁢

⁢

d

q

i

′

·

2

i

)

⊕

q

′

,

 wherein q′ denotes intermediate calculation information derived from a prime number q.

19. The CRT-RSA encryption method of claim 1 , wherein the calculating of the encryption process result comprises:

calculating a calculation value S and a calculation value S′ using the equations S=CRT FA (R S p ,R S q )=m d −(d′ p ⊕d q )mod N and S′=CRT FA (R′ S p ,R′ S q )=m d-1 −(d′ p ⊕d′ q )mod N by using the modular exponential calculation results; and

outputting an encrypted result based on a comparison result of the calculation value S and the calculation value S′,

wherein R S p and R′ S p are values calculated during the modular exponential calculations based on the first parameter d′ p , R S q and R′ S q are values calculated during the modular exponential calculations based on the second parameter d′ q , and m is a message.

20. A Chinese Remainder Theorem (CRT)-Rivest Shamir Adleman (RSA) (CT_RSA) encryption apparatus, comprising:

a register block that stores input information necessary for encryption processes and intermediate calculation information generated during encryption calculation processes;

an intermediate value calculator that calculates intermediate calculation information including first parameter information and second parameter information for determining an exponentiation operation value about a message in a modular exponential calculation process by applying input information read from the register block;

an information partition processing unit that divides the first parameter information and the second parameter information respectively into a plurality of blocks;

a modular multiplier that performs modular exponentiation calculation processes by applying the intermediate calculation information to each of the blocks divided from the first parameter information and the second parameter information through a plurality of calculating iterations;

a CRT calculator that performs a CRT calculation using results of the modular exponential calculation; and

an encryption result calculator that calculates an encryption processing result based on a result of the CRT calculation,

wherein the modular exponential calculation processes include:

extracting a first (1A) block information from the first parameter information;

extracting a second (2A) block information from the second parameter information;

extracting a third (1B) block information remaining, except for the first (1A) block information, from the first parameter information;

extracting a fourth (2B) block information remaining, except for the second (2A) block information, from the second parameter information; and

performing a plurality of modular exponential calculations based on the first (1A) through fourth (2B) block information.