Importance

Loading Importance Indicators...

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.sub.1, x.sub.2, . . . , x.sub.n }, where x.sub.i [0, 2.sup.s). Then the ciphertext {y.sub.1, y.sub.2, . . . , y.sub.m } is determined by ##EQU1## mod q.sub.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.sub.ij, g.sub.j, and positive fractions f.sub.i, for i=1 to n and for j=1 to m, and positive integers q.sub.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.sub.1, b.sub.2, . . . , b.sub.n } and target value b.ident..vertline.w.sup.-1 .vertline.w'.sup.-1 y.vertline..sub.Q .vertline..sub.P, where y.ident.{y.sub.1, y.sub.2, . . . , y.sub.m } mod {q.sub.1, q.sub.2, . . . , q.sub.m }, ##EQU5## and w, w', and {q.sub.m'+1, q.sub.m'+2, . . . , q.sub.m } are secret integers. The resulting terms {x'.sub.1, x'.sub.2, . . . , x'.sub.n } correspond to the original message terms {x.sub.1, x.sub.2, . . . , x.sub.n }.

Loading the Abstract Image...

First Claim