Cryptographic method for communication and electronic signatures

A cryptographic communication system comprising:

• A. a communications channel;
• B. an encoder coupled to the channel and adapted for transforming a message {x.sub.1, x.sub.2, . . . , x.sub.n } to a ciphertext {y.sub.1, y.sub.2, . . . , y.sub.m } on the channel, where {x.sub.1, x.sub.2, . . . , x.sub.n } corresponds to a set of integers representative of the message and
• x.sub.i [0,2.sup.s),
• for i=1 to n, where n.gtoreq.2 and s is some positive integer, and where {y.sub.1, y.sub.2, . . . , y.sub.m } corresponds to a set of integers representative of an enciphered form of the message and corresponds to ##EQU82## where 1.ltoreq.m'<m and r.gtoreq.2, and where an encoding key contains the integers a.sub.ij, g.sub.lj.sup.k, and fractions f.sub.il.sup.k and f.sub.j,l.sup.h,k, for i=1 to n, j=1 to m, l=1 to m.sup.k, k=1 to r-1, and h=1 to k-1, and q.sub.j, for j=1 to m', wherein
• a.sub.ij .ident.a.sub.i.sup.r mod q.sub.j,
• where a.sub.i.sup.r is obtained by performing r iterations of modular multiplication according to the relation
• a.sub.i.sup.k+1 .ident.a.sub.ij.sup.k+1 mod p.sub.j.sup.k+1 .ident.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.sup.k and k=1 to r, where a.sub.i.sup.0 =b.sub.i, for i=1 to n, and ##EQU83## where p.sub.j,l.sup.h,k is obtained by modular multiplying p.sub.j.sup.h to modulus p.sub.l.sup.k according to the same relations followed by a.sub.ij.sup.h, and where a set of initial knapsack weights {b.sub.1, b.sub.2, . . . , b.sub.n }={a.sub.1.sup.0, a.sub.2.sup.0, . . . , a.sub.n.sup.0 } is selected as a superincreasing series according to the relation ##EQU84## and where ##EQU85## where k [1, r-1], and where m.sup.r-1 =1 and m.sup.r =m, and where ##EQU86## and where A.sub.l.sup.k has an approximation error bounded by [-2.sup.-e-1, 2.sup.-e-1) before truncation, and where {q.sub.1, q.sub.2, . . . , q.sub.m } are pairwise relatively prime and ##EQU87## and, where p.sup.1 is relatively prime to b.sub.i, for i=1 to n, and where p.sup.k-1 and p.sup.k are relatively prime, for k=2 to r, and where w.sup.k and p.sup.k are relatively prime, for k=1 to r;
• C. a decoder coupled to the channel and adapted for receiving the ciphertext {y.sub.1, y.sub.2, . . . , y.sub.m } from the channel and for transforming {y.sub.1, y.sub.2, . . . , y.sub.m } to a deciphered message {x'.sub.1, x'.sub.2, . . . , x'.sub.n }, wherein the deciphered message {x'.sub.1, x'.sub.2, . . . , x'.sub.n } corresponds to a set of numbers representative of a deciphered form of the ciphertext {y.sub.1, y.sub.2, . . . , y.sub.m }, and where {y.sub.1, y.sub.2, . . . , y.sub.m } is decoded by first calculating
• y.sub.j.sup.k .ident.(w.sup.k+1).sup.-1 y.sub.j.sup.k+1 mod p.sub.j.sup.k+1,
• for j=1 to m.sup.k and decrementing from k=r-1 to 0, where y.sup.r .ident.{y.sub.1, y.sub.2, . . . , y.sub.m } mod {q.sub.1, q.sub.2, . . . , q.sub.m }, and then solving a knapsack problem, ##EQU88## with the set of initial knapsack weights {b.sub.1, b.sub.2, . . . , b.sub.n } and target value b=y.sup.0, by calculating sequentially ##EQU89## from i=n decrementing to 1, to return the deciphered message {x'.sub.1, x'.sub.2, . . . , x'.sub.n }, and where a decoding key includes the positive integers {b.sub.1, b.sub.2, . . . , b.sub.n }, {w.sub.1, w.sub.2, . . . , w.sub.r }, {p.sup.1, p.sup.2, . . . , p.sup.r }, and {q.sub.1, q.sub.2, . . . , q.sub.m }.