Cryptographic method for communication and electronic signatures

• US 5,297,206 A
• Filed: 10/07/1992
• Issued: 03/22/1994
• Est. Priority Date: 03/19/1992
• Status: Expired due to Fees

• Current Assignee: Glenn A. Orton
• Original Assignee: Glenn A. Orton
• Inventors: Orton, Glenn A.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US07/957,105
• Time in Patent Office: 531 Days
• Field of Search: 380/30, 380/23-25, 380/28
• US Class Current: 380/30
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

A cryptographic method for communication and electronic signatures is described. The system includes at least one encoding device coupled to at least one decoding device by a communications channel. The method is a form of public-key or two-key cryptosystem, where the private decoding key is not feasibly determinable from the associated public encoding key. A block of ns bits of a message-to-be-transferred M (or key-to-be-distributed) is enciphered to ciphertext by first mapping M to a set {x₁, x₂, . . . , x_n }, where x_i [0, 2^s). Then the ciphertext {y₁, y₂, . . . , y_m } is determined by ##EQU1## mod q_j, for j=1 to m'"'"', and ##EQU2## for j=m'"'"'+1 to m, where ##EQU3## The encoding key (associated with the intended receiver) consists of integers a_ij, g_j, and positive fractions f_i, for i=1 to n and for j=1 to m, and positive integers q_j, for j=1 to m'"'"'. The ciphertext is deciphered (with a secret key known only to the intended receiver) by solving a knapsack ##EQU4## with secret superincreasing weights {b₁, b₂, . . . , b_n } and target value b≡|w^-1 |w'"'"'^-1 y|_Q |_P, where y≡{y₁, y₂, . . . , y_m } mod {q₁, q₂, . . . , q_m }, ##EQU5## and w, w'"'"', and {q_m'"'"'+1, q_m'"'"'+2, . . . , q_m } are secret integers. The resulting terms {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n } correspond to the original message terms {x₁, x₂, . . . , x_n }.

Claims

1. A cryptographic communication system comprising:

A. a communications channel;

B. an encoder coupled to the channel and adapted for transforming a message {x₁, x₂, . . . , x_n } to a ciphertext {y₁, y₂, . . . , y_m } on the channel, where {x₁, x₂, . . . , x_n } corresponds to a set of integers representative of the message and

space="preserve" listing-type="equation">x.sub.i [0,2.sup.s),

for i=1 to n, where n≧

2 and s is some positive integer, and where {y₁, y₂, . . . , y_m } corresponds to a set of integers representative of an enciphered form of the message and corresponds to ##EQU82## where 1≦

m'"'"'<

m and r≧

2, and where an encoding key contains the integers a_ij, g_lj^k, and fractions f_il^k and f_j,l^h,k, for i=1 to n, j=1 to m, l=1 to m^k, k=1 to r-1, and h=1 to k-1, and q_j, for j=1 to m'"'"', wherein

space="preserve" listing-type="equation">a.sub.ij ≡

a.sub.i.sup.r mod q.sub.j,

where a_i^r is obtained by performing r iterations of modular multiplication according to the relation

space="preserve" listing-type="equation">a.sub.i.sup.k+1 ≡

a.sub.ij.sup.k+1 mod p.sub.j.sup.k+1 ≡

w.sup.k+1 (a.sub.i.sup.k mod p.sub.j.sup.k) mod p.sub.j.sup.k+1,

for j=1 to m^k and k=1 to r, where a_i⁰ =b_i, for i=1 to n, and ##EQU83## where p_j,l^h,k is obtained by modular multiplying p_j^h to modulus p_l^k according to the same relations followed by a_ij^h, and where a set of initial knapsack weights {b₁, b₂, . . . , b_n }={a₁⁰, a₂⁰, . . . , a_n⁰ } is selected as a superincreasing series according to the relation ##EQU84## and where ##EQU85## where k [1, r-1], and where m^r-1 =1 and m^r =m, and where ##EQU86## and where A_l^k has an approximation error bounded by [-2^-e-1, 2^-e-1) before truncation, and where {q₁, q₂, . . . , q_m } are pairwise relatively prime and ##EQU87## and, where p¹ is relatively prime to b_i, for i=1 to n, and where p^k-1 and p^k are relatively prime, for k=2 to r, and where w^k and p^k are relatively prime, for k=1 to r;

C. a decoder coupled to the channel and adapted for receiving the ciphertext {y₁, y₂, . . . , y_m } from the channel and for transforming {y₁, y₂, . . . , y_m } to a deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n }, wherein the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n } corresponds to a set of numbers representative of a deciphered form of the ciphertext {y₁, y₂, . . . , y_m }, and where {y₁, y₂, . . . , y_m } is decoded by first calculating

space="preserve" listing-type="equation">y.sub.j.sup.k ≡

(w.sup.k+1).sup.-1 y.sub.j.sup.k+1 mod p.sub.j.sup.k+1,

for j=1 to m^k and decrementing from k=r-1 to 0, where y^r ≡

{y₁, y₂, . . . , y_m } mod {q₁, q₂, . . . , q_m }, and then solving a knapsack problem, ##EQU88## with the set of initial knapsack weights {b₁, b₂, . . . , b_n } and target value b=y⁰, by calculating sequentially ##EQU89## from i=n decrementing to 1, to return the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n }, and where a decoding key includes the positive integers {b₁, b₂, . . . , b_n }, {w₁, w₂, . . . , w_r }, {p¹, p², . . . , p^r }, and {q₁, q₂, . . . , q_m }.

2. A system as claimed in claim 1, wherein m^k =1, for k=1 to r, and where the cryptographic communication system under the limitation of m^k =1, for k=1 to r, comprises:

A. the communications channel;

B. the encoder, where the message {x₁, x₂, . . . , x_n } is encoded according to the relations ##EQU90## where x_i [0, 2^s), for i=1 to n, where n≧

2 and s is some positive integer, and where 1≦

m'"'"'<

m and r≧

2, and where the encoding key contains the integers a_ij, g_j^k, and fractions f_i^k and f^h,k, for i=1 to n, j=1 to m, k=1 to r-1, and h=1 to k-1, and q_j, for j=1 to m'"'"', wherein

space="preserve" listing-type="equation">a.sub.ij ≡

a.sub.i.sup.r mod q.sub.j,

where a_i^r is obtained by performing r iterations of modular multiplication according to the relation

space="preserve" listing-type="equation">a.sub.i.sup.k ≡

w.sup.k a.sub.i.sup.k-1 mod p.sup.k,

from k=1 to r, where a_i⁰ =b_i, for i=1 to n, and ##EQU91## where p^h,k is obtained by calculating p^h, h+1 ≡

w^h+1 p^h mod p^h+1, p^h,h+2 ≡

w^h+2 p^h,h+1 mod p^h+2, . . . , p^h, k ≡

w^k p^h,k-1 mod p^k, and

space="preserve" listing-type="equation">g.sub.j.sup.k ≡

p.sup.k,r mod q.sub.j,

and where the set of initial knapsack weights {b₁, b₂, . . . , b_n }={a₁⁰, a₂⁰, . . . , a_n⁰ } is selected as the superincreasing series according to the relations ##EQU92## where A_x^k has an approximation error bounded by [-2^-e-1, 2^-e-1) before truncation and the fractions f_i^k and f^h,k, for i=1 to n, k=1 to r-1, and h=1 to k-1, are published to s+log₂ (n)+k-1+e bits precision, where e is a positive number, and where {q₁, q₂, . . . , q_m } are pairwise relatively prime and ##EQU93## and, where p¹ is relatively prime to b_i, for i=1 to n, and where p^k-1 and p^k are relatively prime, for k=2 to r, and where w^k and p^k are relatively prime, for k=1 to r;

C. the decoder where the ciphertext {y₁, y₂, . . . , y_m } is decoded by first calculating

space="preserve" listing-type="equation">y.sup.k-1 ≡

y.sup.k (w.sup.k).sup.-1 mod p.sup.k,

from k=r decrementing to 1, where y^r ≡

{y₁, y₂, . . . , y_m } mod {q₁, q₂, . . . , q_m }, and then solving the knapsack problem, ##EQU94## with the set of initial knapsack weights {b₁, b₂, . . . , b_n } and target value b=y⁰, by calculating sequentially ##EQU95## from i=n decrementing to 1, to return the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n }, and where the decoding key includes the positive integers {b₁, b₂, . . . , b_n }, {w₁, w₂, . . . , w_r }, {p¹, p², . . . , p^r }, and {q₁, q₂, . . . , q_m }.

3. A system as claimed in claim 1, wherein r=2 and m^k =1, for k=1 to r, and where the cryptographic communication system under the limitations of m^k =1, for k=1 or r, and r=2 comprises:

A. the communications channel;

B. the encoder, where the message {x₁, x₂, . . . , x_n } is encoded according to the relations ##EQU96## where x_i [0, 2^s), for i=1 to n, where n≧

2 and s is some positive integer, and where m≧

2 and 1≦

m'"'"'<

m, and where the encoding key consists of integers a_ij, g_j, and fractions f_i [0.0, 1.0), for i=1 to n and j=1 to m, and q_j, for j=1 to m'"'"', wherein ##EQU97## where with the present notation;

P=p¹, Q=p², w=w¹, w'"'"'=w², and |c|_d is equivalent to c mod d, and where the set of initial knapsack weights {b₁, b₂, . . . , b_n } is the superincreasing series with ##EQU98## and where {q₁, q₂, . . . , q_m } are chosen such that ##EQU99## where A_x has an approximation error bounded by [-2^-e-1, 2^-e-1) before truncation and the fractions f_i, for i=1 to n, are published to s+log₂ n+e bits precision, where e is a positive number, and where P is relatively prime to b_i, for i=1 to n, and where {q₁, q₂, . . . , q_m } are pairwise relatively prime, and where P and Q are relatively prime, and where w and P are relatively prime, and where w'"'"' and Q are relatively prime, and

C. the decoder, where the ciphertext {y₁, y₂, . . . , y_m } is decoded by first calculating

space="preserve" listing-type="equation">b≡

|w.sup.-1 |w'"'"'.sup.-1 y|.sub.Q |.sub.P

where y≡

{y₁, y₂, . . . , y_m } mod {q₁, q₂, . . . , q_m }, and and then solving the knapsack problem ##EQU100## with the set of initial knapsack weights {b₁, b₂, . . . , b_n } by calculating ##EQU101## from i=n decrementing to 1, to return the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n }, and where the decoding key is the positive integers w, w'"'"', {q₁, q₂, . . . , q_m }, {b₁, b₂, . . . , b_n }, and P.

4. The system of claim 1 and further comprising an alternate initial knapsack construction, wherein

the set of initial knapsack weights {b₁, b₂, . . . , b_n } is selected as a partially superincreasing series that contains n" non-superincreasing bands, where a superincreasing series {d₁, d₂, . . . , d_n'"'"' } is first selected according to the relations ##EQU102## (P=p¹) and then {d₁, d₂, . . . , d_n'"'"' } is divided into two subsets S and S*, where S contains any n elements, S* contains the remaining n" elements, and n'"'"'=n+n", and where the set of initial knapsack weights {b₁, b₂, . . . , b_n } is calculated ##EQU103## for i=1 to n, where d_j S, a different value of d_j from subset S is used with each b_i, and r_ik is randomly selected from [0, 2^s.sbsp.i /n), for all k S*, and where the message is assigned to x_i [0, 2^S.sbsp.i), for i=1 to n, and where the decoder decodes the ciphertext by solving the superincreasing series with weights {d₁, d₂, . . . , d_n'"'"' } and target value b and the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n } corresponds to the coefficients of the subset S of {d₁, d₂, . . . , d_n'"'"' }.

5. The system of claim 1 and further comprising an alternate initial knapsack construction, wherein

P=p¹ is selected as a residue number system, where ##EQU104## and {p₁, p₂, . . . , p_n } are chosen randomly from an interval p_i [2^d, 2^d +v), for i=1 to n, where d and v are positive integers, and where {p₁, p₂, . . . , p_n } are pairwise relatively prime, and where the set of initial knapsack weights {b₁, b₂, . . . , b_n } are generated by first selecting a matrix ##EQU105## where b_ij, for i=1 to n and j=1 to n, are randomly chosen from the range b_ij [0, 2^z) such that the matrix b is nonsingular and invertable and the sum of each column of b is less than 2^z, and where the set of initial knapsack weights {b₁, b₂, . . . , b_n } are defined by the relation b_i ≡

{b_i1, b_i2, . . . , b_in } mod {p₁, p₂, . . . , p_n } and the residues {b_i1, b_i2, . . . , b_in } can be recombined by the Chinese remainder theorem according to the relation ##EQU106## where P_j =P/p_j, and where the message {x₁, x₂, . . . , x_n } satisfies x_i <

2^s, for i=1 to n, and where d≧

s+z, and where n≧

2 and r≧

2, and where the decoder calculates x"_i =y⁰ mod p_i, for i=1 to n, and then a matrix multiplication x'"'"'=x"·

b^-1 is performed, where x'"'"'=(x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n) and x"=(x"₁, x"₂, . . . , x"_n), and where the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n } is congruent to the message {x₁, x₂, . . . , x_n } modulo {p₁, p₂, . . . , p_n }.

6. The system of claim 5, wherein

the matrix b is selected as an identity matrix and b_i =P_i (P_i^-1 mod p_i), for i=1 to n, where P_j =P/p_j and n≧

2.

7. The system of claim 5, wherein

the matrix b is selected with dimensions n-1 by n-1 and b_ij [0, 2^s), for i=1 to n-1 and j=1 to n-1, and where ##EQU107## p_i ≧

2^d, and d≧

s+z, and where b_i ≡

{b_i1, b_i2, . . . , b_in-1 } mod {p₁, p₂, . . . , p_n-1 }, for i=1 to n-1, and b_n =1, and where the message is assigned to x_n [0, 2^s) and random bits are assigned to x_i [0, 2^z), for i=1 to n-1 to n-1, and where the decoder calculates x'"'"'=x"·

b^-1, where x'"'"'=(x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n-1) are rational numbers and then the deciphered message is ##EQU108## where i is any integer from the range [1, n-1) and u_i =0 if the sum of the ith column of b^-1 is positive (i.e. if ##EQU109## and u_i =1 otherwise.

8. The system of claim 1 and further comprising an alternate initial knapsack construction, wherein

the set of initial knapsack weights is {b₁, b₂ }={1, p₁ |p₁^-1 |_p2 }, and where the message is assigned to {x₁, x₂ }, where x_i [0, 2^s), and x₂ >

x₁, and the encoder calculates the ciphertext corresponding to a message of {x₁, x₂ -x₁ }, and where n=2 and r≧

2, and where the decoder calculates x'"'"'_i =y⁰ mod p_i, for i=1 to n, and where the deciphered message {x'"'"'₁, x'"'"'₂ } is congruent to the original message {x₁, x₂ } modulo {p₁, p₂ }.

9. The system of claim 2 and further comprising an alternate decoder with double-encryption, wherein

the alternate decoder first maps the ciphertext {y₁, y₂, . . . , y_m } to {z₁, z₂, . . . , z_n }, where ##EQU110## z_i [0, 2^s), for i=1 to n, and s is a positive integer, and where b is calculated according to the relations ##EQU111## and where c^h,k is obtained by calculating c^h,h+1 ≡

(w^h+1)^-1 c^h mod c^h+1, c^h,h+2 ≡

(w^h+2)^-1 c^h,h+1 mod c^h+2, . . . , c^h,k ≡

(w^k)^-1 c^h,k-1 mod c^k, and where a_i =a_i and b_i =a_i⁰, and where

space="preserve" listing-type="equation">b.sub.i =Q.sub.j |2.sup.s(i-d.sbsp.j-1.sup.-1) Q.sub.j.sup.-1 |.sub.qj,

where Q=p^r, Q_j =Q/q_j, and u_j-1 <

i≦

u_j, and where the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n } is obtained by solving the knapsack problem ##EQU112## with the set of initial knapsack weights {b₁, b₂, . . . , b_n }, and where p^k (1-2^-e)>

p^k-1 (1+2^-e), for k=2 to r, and the fractions f_i^k and f^h,k, for i=1 to n, k=1 to r-1, and h=1 to k-1, are precise to s+log₂ (n+k-1)+e bits.

10. A system as claimed in claim 9, wherein r=2, and

where the alternate decoder under the limitation of r=2 calculates b according to the relations ##EQU113## where with the present notation:

P=p¹, Q=p², w=w¹, w'"'"'=w², and |c|_d is equivalent to c mod d, and where Q(1-2^-e)>

P(1+2^-e) and the fractions f_i, for i=1 to n, are precise to s+log₂ n+e bits.

11. The system of claim 1, wherein the encoder and the decoder comprises:

at least one of the group consisting of;

microprocessor, parallel processor, computer, and integrated circuits, and at least one of the group consisting of;

registers for storing inputs and outputs of the encoder and decoder and constants related to the key;

adders, multipliers, modular multipliers, and modular reduction circuits; and

write-only registers for storing the secret key, and where the encoder and the decoder are part of a cryptographic communication and/or identification system.

12. The system of claim 2 and further comprising a shortened encoding key, wherein

a subset of the variables in the encoding key are standardized during key-generation, where the standardized subset of the encoding key of each user in a network is identical, and where the encoding key as defined in claim 2 is a_ij, g_j^k, and fractions f_i^k and f^h,k, for i=1 to n, j=1 to m, k=1 to r-1, and h=1 to k-1, and q_j, for j=1 to m'"'"', and where {q₁, q₂, . . . , q_m'"'"' } is standardized, and where one weight {a_v1, a_v2, . . . , a_vm } is standardized, where v is one of the integer values in the range [1, n], and where g_j^k, for k=1 to r-1 and j=1 to m, are standardized, and where the standardized values of a_vj and g_j^k, for k=1 to r-1 and j=1 to m, are randomly selected from the range [0, q_j), and where {b₁, b₂, . . . , b_n }, {p¹, p², . . . , p^r }, and {q_m'"'"'+1, q_m'"'"'+2, . . . , q_m } are selected as specified in claim 2 and are not standardized, and where {w¹, w², . . . , w^r } are next calculated sequentially according to the relation

13. The system of claim 3 and further comprising a shortened encoding key, wherein

a subset of the variables in the encoding key are standardized during key-generation, where the standardized subset of the encoding key of each user in a network is identical, and where the encoding key as defined in claim 3 is {a_i1, a_i2, . . . , a_im }, for i=1 to n, {g₁, g₂, . . . , g_m }, {f₁, f₂, . . . , f_n }, and {q₁, q₂, . . . , q_m'"'"' }, and where {q₁, q₂, . . . , q_m'"'"' } is standardized, and where {a_n1, a_n2, . . . , a_nm } and {g₁, g₂, . . . , g_m } are standardized by randomly selecting a_nj and g_j from the range [0, q_j), for j=1 to m, and where P, {b₁, b₂, . . . , b_n }, and {q_m'"'"'+1, q_m'"'"'+2, . . . , q_m } are selected as specified in claim 3 and are not standardized, and where w'"'"' is found according to the relation

14. The system of claim 2 and further comprising a signature verification, wherein

a sender generates a signature of the message with the decoder and the decoding key of the sender, where n≧

1 and r≧

2, and where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } by a blocking method, where y_j [0, q_j) for j=1 to m'"'"', and 1≦

m'"'"', and 1≦

m'"'"'<

m, and where at least one of the following group;

secret random integers, secret pseudo-random integers, secret non-random integers, and non-secret integers that are constant for all signatures, are assigned to {y_m'"'"'+1, y_m'"'"'+2, . . . , y_m }, where y_j [0, q_j) for j=m'"'"'+1 to m, and where decoding {y₁, y₂, . . . , y_m } with the decoder and the decoding key of the sender yields the signature {x₁, x₂, . . . , x_n } , and where the sender then checks if x_j <

2^s, for j=1 to n, and if this test is failed, then decoding {y₁, y₂, . . . , y_m } is repeated with a different value of {y_m'"'"'+1, y_m'"'"'+2, . . . , y_m }, and where the signature and the message are sent to a receiver along the communications channel, and

the signature {x₁, x₂, . . . , x_n } is checked by the receiver or by a third party by encoding {x₁, x₂, . . . , x_n } to {y'"'"'₁, y'"'"'₂, . . . , y'"'"'_m'"'"' } with the encoder and the encoding key of the sender, and where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } with the blocking method, and where the signature is valid if ##EQU114## for j=1 to m'"'"', where d^k [-1, [p^k+1 /p^k ]+1].

15. The system of claim 2 and further comprising a signature verification, wherein

a sender generates a signature of the message with the decoder and the decoding key of the sender by assigning the message to {y₁, y₂, . . . , y_m'"'"' } with a blocking method, where y_j [0, q_j) for j=1 to m'"'"', and where n≧

1 and r≧

2, and where an integer c is selected from one of the group consisting of;

a secret random integer, a secret non-random integer, and a fixed public integer, and where c [p^r-1 2^-e /q,p^r-1 /q), where ##EQU115## and where y^r mod q and c are combined according to the relation

space="preserve" listing-type="equation">y.sup.r-1 =|(w.sup.r).sup.-1 y.sup.r |q+cq,

where y^r ≡

{y₁, y₂, . . . , y_m'"'"' } mod {q₁, q₂, . . . , q_m'"'"' }, and where y^r-1 is an intermediate value in the decoder and decoding is completed from y^r-1 by the decoder to generate the signature {x₁, x₂, . . . , x_n }, and where decoding y^r-1 is repeated with a different value of c if x_j ≧

2^s, for j=1 to n, and where the signature and the message are sent to a receiver along the communications channel, and

the signature {x₁, x₂, . . . , x_n } is checked by the receiver or by a third party by encoding {x₁, x₂, . . . , x_n } to {y'"'"'₁, y'"'"'₂, . . . , y'"'"'_m'"'"' } with the encoder and the encoding key of the sender, and where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } with the blocking method, and where the signature is valid if ##EQU116## for j=1 to m'"'"', where d^k [-1, [p^k+1 /p^k ]+1].

16. A method as claimed in claim 15, wherein m'"'"'=1 and r=2.

17. The system of claim 2 and further comprising a signature verification, wherein

a sender generates a signature of the message with the decoder and the decoding key of the sender, where n≧

1 and r≧

2, and where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } by a blocking method, where y_j [0 q_j) for j=1 to m'"'"', and 1≦

m'"'"'<

m, and where at least one of;

secret random integers, secret pseudo-random integers, secret non-random integers, and non-secret integers that are constant for all signatures, are assigned to {y_m'"'"'+1, y_m'"'"'+2, . . . , y_m }, where y_j [0, q_j) for j=m'"'"'+1 to m, and where decoding {y₁, y₂, . . . , y_m } with the decoder and the decoding key of the sender yields the signature {x₁, x₂, . . . , x_n }, where the decoding key is selected with p.sup. k >

p^k+1 (1+2^-e), for k=1 to r-1, and where decoding }y₁, y₂, . . . y_m } is repeated with a different value of {y_m'"'"'+1, y_m'"'"'+2, . . . , y_m } if x_j ≧

2^s, for j=1 to n, and where the signature and the message are sent to a receiver along the communications channel, and

the signature {x₁, x₂, . . . , x_n } is checked by the receiver or by a third party by encoding {x₁, x₂, . . . , x_n } to {y'"'"'₁, y'"'"'₂, . . . , y'"'"'_m'"'"' } with the encoder and the encoding key of the sender, where the encoder calculates A_x^k during signature checking according to ##EQU117## and, where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } with the blocking method, and where the signature is valid if y_j ≡

y'"'"'_j mod q_j, for j=1 to m'"'"'.

18. The system of claim 2 and further comprising an abbreviated signature, wherein

a sender generates a signature of the message with the decoder using the decoding key of the sender, where n≧

1 and r≧

2, and where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } by a blocking method, where y_j [0, q_j) for j=1 to m'"'"', and 1≦

m'"'"'<

m, and where at least one of;

secret random integers, secret pseudo-random integers, secret non-random integers, and non-secret integers that are constant for all signatures, are assigned to {y_m'"'"'+1, y_m'"'"'+2, . . . , y_m }, where y_j [0, q_j) for j=m'"'"'+1 to m, and where decoding {y₁, y₂, . . . , y_m } with the decoder and the decoding key of the sender yields the signature {x₁, x₂, . . . , x_n }, where the decoding key is selected with p.sup. k >

p^k+1 (1+2^-e), for k=1 to k'"'"'-1 and k'"'"'+1 to r-1, where k'"'"' is one value from [1, r-1], and where the signature is abbreviated by selecting p^k'"'"' <

p^k'"'"'+1, and where decoding {y₁, y₂, . . . , y_m } is repeated with a different value of {y_m'"'"'+1, y_m'"'"'+2, . . . , y_m } if x_j ≧

2^s, for j=1 to n, and where the signature and the message are sent to a receiver along the communications channel, and

the signature {x₁, x₂, . . . , x_n } is checked by the receiver or by a third party by encoding {x₁, x₂, . . . , x_n } to {y'"'"'₁, y'"'"'₂, . . . , y'"'"'_m'"'"' } with the encoder and the encoding key of the sender, where the encoder calculates A_x^k during signature checking according to ##EQU118## and, where the message is assigned to {y₁, y₂, . . . , y_m'"'"' } with the blocking method, and where the signature is valid if y≡

y'"'"'+dg^k'"'"' mod q with d [-1, [p^k'"'"'+1 /p^k'"'"' ]+1], where d≡

(g^k'"'"')^-1 (y'"'"'-y) mod q, y≡

{y₁, y₂, . . . , y_m'"'"' } mod {q₁, q₂, . . . , q_m'"'"' }, y'"'"'≡

{y'"'"'₁, y'"'"'₂, . . . , y'"'"'_m'"'"' } mod {q₁, q₂, . . . , q_m'"'"' }, and ##EQU119##

19. The system of claim 14 and further comprising an identity verification, wherein

a party (the verifier) wishes to verify a claimed identity of a second party (the candidate) and the verifier generates a secret random number and sends the secret random number to the candidate along the communications channel, and

the candidate then generates the signature of the message, where the message is set equal to the secret random number, with the decoder and the decoding key of the candidate and sends the signature along the communications channel to the verifier, and

the verifier then verifies if the signature of the secret random number is valid with the encoder and the encoding key of the candidate, and the claimed identity is true if the signature of the secret random number is valid.

20. The system of claim 1 and further comprising an identity verification, wherein

a party (the verifier) wishes to verify a claimed identity of a second party (the candidate) and the verifier generates a secret random number and the message is set equal to the secret random number, and where the verifier assigns the message to {x₁, x₂, . . . , x_n }, where x_j [0, 2^s), for j=1 to n, and where the verifier encodes the message {x₁, x₂, . . . , x_n } to the ciphertext {y₁, y₂, . . . , y_m } with the encoder and the encoding key of the candidate and sends {y₁, y₂, . . . , y_m } to the candidate along the communications channel, and

the candidate decodes {y₁, y₂, . . . , y_m } with the decoder and the decoding key of the candidate to obtain the deciphered message {x'"'"'₁, x'"'"'₂, . . . , x'"'"'_n } and the candidate sends {x"₁, x"₂, . . . , x"_n } to the verifier along the communications channel, where x"_j =x'"'"'_j mod 2^s" j and s"_j ≦

s, for j=1 to n, and

the verifier determines that the claimed identity of the candidate is true if x"_j ≡

x_j mod 2^s" j, for j=1 to n.