Method of and apparatus for encryption and decryption of communication data

A cryptic communication method using a communication apparatus which performs encryption or decryption of a communication data by using a modular exponentiation C=M.sup.e mod N concerning integers M and e using N as the modulus, said communication apparatus having at least one computing unit which computes and outputs Z=U.multidot.V.multidot.R.sup.-1 mod N by using, with respect to input data U and V, an integer R which is prime to N, said method comprising the steps of:

• inputting to one of said computing units M and a constant R.sub.R which is expressed by R.sub.R =R.sup.2 mod N, thereby causing said computing unit to output M.sub.R =M.multidot.R.sub.R .multidot.R.sup.-1 mod N;
• representing the binary expression of e by e=[e.sup.t, e.sup.t-1, . . . , e.sup.1 ], determining the values of e.sup.i starting from the lowest order bit;
• representing the initial value of C.sub.R by R.sub.R .multidot.R.sup.-1 mod N, inputting C.sub.R and M.sub.R to one of said computing units when e.sup.i is determined to be equal to e.sup.i =1, thereby causing said computing unit to output C.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N as a new C.sub.R ;
• determining whether i of said e.sup.i is greater than 1 or not;
• inputting, when i is greater than 1, C.sub.R as two input data to one of said computing unit, thereby causing said computing unit to output, as new value of C.sub.R, C.sub.R .multidot.C.sub.R .multidot.R.sup.-1 mod N;
• and
• after completion of processing on all e.sup.i, inputting the C.sub.R and 1 as a constant to one of said computing units, thereby causing said computing unit to output, as the aimed C, C=C.sub.R .multidot.1.multidot.R.sup.-1 mod N, whereby said modular exponentiation C=M.sup.3 mod N is executed.

A cryptic communication method using a communication apparatus which performs encryption or decryption of communication data by using a modular exponentiation C=M.sup.3 mod N concerning integers M and e using N as the modulus, said communication apparatus having at least one computing unit which computes and outputs Z=U.multidot.V.multidot.R.sup.-1 mod N by using, with respect to input data U and V, an integer R which is prime to N, said method comprising the steps of:

• inputting to one of said computing units M and a constant R.sub.R which is expressed by R.sub.R =R.sup.2 mod N, thereby causing said computing unit to output M.sub.R =M.multidot.R.sub.R .multidot.R.sup.-1 mod N;
• representing the binary expression of e by e=[e.sup.t,e.sup.t-1, . . . , e.sup.1 ], determining the values of e.sup.i starting from the highest order bit;
• representing the initial value of C.sub.R by R.sub.R .multidot.R.sup.-1 mod N, inputting C.sub.R and M.sub.R to one of said computing units when e.sup.i is determined to be equal to 1, thereby causing said computing unit to output C.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N as a new C.sub.R ;
• determining whether i of said e.sup.i is greater than t or not;
• inputting, when i is smaller than t, M.sub.R as two input data to one of said computing units, thereby causing said computing unit to output, as a new value of M.sub.R, M.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N;
• and
• after completion of processing on all e.sup.i, inputting C.sub.R and 1 as a constant to one of said computing units, thereby causing said computing unit to output, as the aimed C, C=C.sub.R .multidot.b.multidot.R.sup.-1 mod N, whereby said modular exponentiation C=M.sup.e mod N is executed.

A cryptic communication method which employs encryption or decryption of a communication data by employing a modular multiplication Q=A.multidot.B mod N for input integers A and B using N as the modulus, said method comprising the steps of:

• computing A.multidot.R mod N using the input A and an integer R which is prime to N, thus determining A.sub.R as the computation result;
• computing B.multidot.R mod N using the input B and said R, thus determining B.sub.R as the computation result;
• computing A.sub.R .multidot.B.sub.R .multidot.R.sup.-1 mod N on the basis of said computing results A.sub.R and B.sub.R and said R, thus determining T.sub.R as the computation result;
• and
• computing T.sub.R .multidot.R.sup.-1 mod N on the basis of said T.sub.R and said R, thus determining said Q as the computation result;
• wherein the computation for determining said T.sub.R is executing by successively computing:
• T.sub.i =(T.sub.i-1 +A.sub.i .multidot.B.sub.R .multidot.Y+M.sub.i-1 N)/Y
• M.sub.i-1 =(T.sub.i-1 mod Y).multidot.(-N.sup.-1 mod Y) mod Y
• wherein Y equals to 2.sup.v and A.sub.i are sections of A.sub.R obtained by dividing A.sub.R for every v bits, where v is an optional integer.

A cryptic communication method which employs encryption or decryption of a communication data by employing a modular multiplication Q=A.multidot.B mod N for input integers A and B using N as the modulus, said method comprising the steps of:

• computing A.multidot.R mod N using the input A and an integer R which is prime to N, thus determining A.sub.R as the computation result;
• computing B.multidot.R mod N using the input B and said R, thus determining B.sub.R as the computation result;
• computing A.sub.R .multidot.B.sub.R .multidot.R.sup.-1 mod N on the basis of said computing results A.sub.R and B.sub.R and said R, thus determining T.sub.R as the computation result;
• and
• computing T.sub.R .multidot.R.sup.-1 mod N on the basis of said T.sub.R and said R, thus determining said Q as the computation result;
• wherein the computation for determining said T.sub.R is executing by successively computing:
• T.sub.i =(T.sub.i-1 /Y+A.sub.i .multidot.B.sub.R .multidot.)+M.sub.i .multidot.N
• M.sub.i-1 =(T.sub.i-1 /Y+A.sub.i .multidot.B.sub.R)mod Y).multidot.(-N.sup.-1 mod Y) mod Y
• wherein Y equals to 2.sup.v and A.sub.i are sections of A.sub.R obtained by dividing A.sub.R for every v bits, where v is an optional integer.

A communication apparatus which performs encryption or decryption of a communication data by executing a modular multiplication A.multidot.B mod N of integers A and B by using N as the modulus, said communication apparatus comprising:

• first computing means for computing A.sub.R =A.multidot.R.sub.R .multidot.R.sup.-1 mod N, upon receipt of A and a constant R.sub.R which is expressed by R.sub.R =R.sup.2 mod N, where R is an integer prime to N;
• second computing means for computing B.sub.R =B.multidot.R.sub.R .multidot.R.sup.-1 mod N upon receipt of said constant R.sub.R and B;
• third computing means for computing T.sub.R =A.sub.R .multidot.B.sub.R .multidot.R.sup.-1 mod N upon receipt of A.sub.R and B.sub.R output from said first and second computing means;
• and
• fourth computing means for computing T.sub.R .multidot.1.multidot.R.sup.-1 mod N and outputting the computation result as said Q, upon receipt of TR output from said third computing means and a constant 1.

A communication apparatus which performs encryption or decryption of a communication data by using a modular exponentiation C=M.sup.e mod N concerning integers M and e using N as the modulus, said communication apparatus comprising:

• first computing means for computing M.sub.R =M.multidot.R.sub.R .multidot.R.sup.-1 mod N upon receipt of M and a constant R.sub.R which is expressed by R.sub.R =R.sup.2 mod N, where R is an integer prime to N;
• first determining means for determining the values of e.sup.i starting from the highest order bit, wherein the binary expression of e is expressed by by e=[e.sup.t, e.sup.t-1, . . . , e.sup.1 ];
• storage means for updating and storing the value of C.sub.R by using C.sub.R =R.sub.R .multidot.R.sup.-1 mod N as the initial value;
• second computing means which receives the C.sub.R stored in said storage means and M.sub.R computed by said first computing means when e.sup.i is determined to be equal to e.sup.i =1, thereby causing said computing unit to output C.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N as a new C.sub.R ;
• second determining means for determining whether i of e.sup.i is greater than 1;
• third computing means for receiving C.sub.R when i is determined by said second determining means to be greater than 1, and outputting, as new value of C.sub.R, C.sub.R .multidot.C.sub.R .multidot.R.sup.-1 mod N;
• and
• fourth computing means which computes, upon receipt of Cr stored in said storage means and 1 as a constant, C=C.sub.R .multidot.1.multidot.R.sup.-1 mod N after completion of computations performed by said second and third computing means on all the values of e.sup.i, thereby outputting the computation result as said C.

A communication apparatus which performs encryption or decryption of a communication content by using a modular exponentiation C=M.sup.e mod N concerning integers M and e using N as the modulus, said communication apparatus comprising:

• first computing means for computing M.sub.R =M.multidot.R.sub.R .multidot.R.sup.-1 mod N upon receipt of M and a constant RR which is expressed by R.sub.R =R.sup.2 mod N;
• first determining means for determining the values of e.sup.i starting from the lowest order bit, wherein the binary expression of e is expressed by by e=[e.sup.t, e.sup.t-1, . . . , e.sup.1 ];
• first storage means for updating and storing the value of C.sub.R by using C.sub.R =R.sub.R .multidot.R.sup.-1 mod N as the initial value;
• second storage means for updating and storing the value of M.sub.R using the output of said first computing means as the initial value;
• second computing means which receives the C.sub.R stored in said first storage means and M.sub.R computed by said first computing means when e.sup.i is determined to be equal to e.sup.i =1, thereby causing said computing unit to output C.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N as a new C.sub.R ;
• second determining means for determining whether i of e.sup.i is smaller than t;
• third computing means for receiving M.sub.R stored in said second storage means when i is determined by said second determining means to be smaller than t, and outputting, as new value of M.sub.R, M.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N;
• and
• fourth computing means which computes, upon receipt of Cr stored in said first storage means and 1 as a constant, C=C.sub.R .multidot.1.multidot.R.sup.-1 mod N after completion of computations performed by said second and third computing means on all the values of e.sup.i, thereby outputting the computation result as said C.

A cryptic communication method using a communication apparatus which performs encryption or decryption of communication data by using a modular exponentiation C=M.sup.e mod N concerning integers M and e using N as the modulus, said communication apparatus having a computing unit which computes and outputs Z=U.multidot.V.multidot.R.sup.-1 mod N by using, with respect to input data U and V, an integer R which is prime to N, and having a selector which selects the input data for said computing unit, said method comprising the steps of:

• selecting M and a constant R.sub.R which is expressed by R.sub.R =R.sup.2 mod N, by said selector;
• inputting the selected M and R.sub.R to said computing unit, thereby causing said computing unit to output M.sub.R =M.multidot.R.sub.R .multidot.R.sup.-1 mod N to said selector;
• representing the binary expression of e by e=[e.sup.t,e.sup.t-1, . . . , e.sup.1 ], determining the values of e.sup.i starting from the least significant bit;
• representing the initial value of C.sub.R by R.sub.R .multidot.R.sup.-1 mod N, selecting C.sub.R and M.sub.R by said selector when e.sup.i is determined to be equal to 1;
• inputting the selected C.sub.R and M.sub.R to said computing unit, thereby causing said computing unit to output C.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N to said selector as a new C.sub.R ;
• determining whether i of said e.sup.i is greater than 1 or not;
• selecting, when i is greater than 1, C.sub.R as two input data by said selector;
• inputting the selected C.sub.R to said computing unit, thereby causing said computing unit to output C.sub.R .multidot.C.sub.R .multidot.R.sup.-1 mod N to said selector as a new value of C.sub.R ;
• after completion of processing on all e.sup.i, selecting C.sub.R and 1 by said selector;
• and
• inputting the selected C.sub.R and 1 to said computing unit, thereby causing said computing unit to output, as the aimed C, C=C.sub.R .multidot.1.multidot.R.sup.-1 mod N, whereby said modular exponentiation C=M.sup.e mod N is executed.

A cryptic communication method using a communication apparatus which performs encryption or decryption of communication data by using a modular exponentiation C=M.sup.e mod N concerning integers M and e using N as the modulus, said communication apparatus having a computing unit which computes and outputs Z=U.multidot.V.multidot.R.sup.-1 mod N by using, with respect to input data U and V, an integer R which is prime to N, and having a selector which selects the input data for said computing unit, said method comprising the steps of:

• selecting M and a constant R.sub.R which is expressed by R.sub.R =R.sup.2 mod N, by said selector:
• inputting the selected M and R.sub.R to said computing unit, thereby causing said computing unit to output M.sub.R =M.multidot.R.sub.R .multidot.R.sup.-1 mod N to said selector;
• representing the binary expression of e by e=[e.sup.t,e.sup.t-1, . . . , e.sup.1 ], determining the values of e.sup.i starting from the least significant bit;
• representing the initial value of C.sub.R by R.sub.R .multidot.R.sup.-1 mod N, selecting C.sub.R and M.sub.R by said selector when e.sup.i is determined to be equal to 1;
• inputting the selected C.sub.R and M.sub.R to said computing unit, thereby causing said computing unit to output C.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N to said selector as a new C.sub.R ;
• determining whether i of said e.sup.i is greater than t or not;
• selecting, when i is greater than t, M.sub.R as two input data by said selector;
• inputting the selected C.sub.R to said computing unit, thereby causing said computing unit to output M.sub.R .multidot.M.sub.R .multidot.R.sup.-1 mod N to said selector as a new value of M.sub.R ;
• after completion of processing on all e.sup.i, selecting C.sub.R and 1 by said selector;
• and
• inputting the selected C.sub.R and 1 to said computing unit, thereby causing said computing unit to output, as the aimed C, C=C.sub.R .multidot.1.multidot.R.sup.-1 mod N, whereby said modular exponentiation C=M.sup.e mod N is executed.