Patent ID: 6396926
Filing Date: 2002-05-28
Classification: H04L

Abstract:
A decryption method for decrypting a ciphertext C obtained from a plaintext M according to:Câ‰¡Me(mod n) Using a first secret key given by N(&gE;2) prime numbers p1, p2, a first public key n given by a product p1k1p2k2 . . . pNkN 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 p1âˆ’1, p2âˆ’1, . . . , pNâˆ’1, the method comprising the steps of:obtaining residues Mp1k1, Mp2k2, . . . , MpNkN modulo p1k1p2k2 . . . pNkN, respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN; and recovering the plaintext M by applying Chinese remainder theorem to the residues Mp1k1, Mp2k2, . . . , MpNkN; wherein the ciphertext C is obtained using the first secret key given by two prime numbers p1=p and p2=q and the first public key n given by a product pkq where k=k1; the obtaining step obtains a residue kÃ˜ modulo p and a residue Mq modulo q of the plaintext M, by integer modular exponent calculations of: kÃ˜:=Cdp(mod p); andMq:=Cdp(mod q); where:dp:=d(mod pâˆ’1); anddq:=d(mod qâˆ’1); and obtains a residue Mpk and Mq; andwherein the prescribed loop calculation is carried out by: (a) setting AÃ˜:=KÃ˜; (b) for i=1 to (kâˆ’1), repeatedly calculating: Fi:=(Aiâˆ’1e) (mod p1=1); Ei:=(Câˆ’Fi) (mod p1=1); Bi:=E1/p1 in Z; Ki:=((eF1i)âˆ’1Aiâˆ’1Bi) (mod p); Ai:=A1âˆ’1+pi in Z; and (c) setting Mpk:=Akâˆ’1.