US6081597A — Public key cryptosystem method and apparatus

Claim 1

Independent Claim 132 words

A method for encoding and decoding a digital message m, comprising the steps of: selecting ideals p and q of a ring R; generating elements f and g of the ring R, and generating element F q which is an inverse of f (mod q), and generating element F p which is an inverse of f (mod p); producing a public key that includes h, where h is congruent, mod q, to a product that can be derived using g and F q ; producing a private key from which f and F p can be derived; producing an encoded message e by encoding the message m using the public key and a random element .o slashed.; and producing a decoded message by decoding the encoded message e using the private key.

Claim 2

Independent Claim 132 words

A method for encoding and decoding a digital message m, comprising the steps of: selecting ideals p and q of a ring R; generating elements f and g of the ring R, and generating element F q which is an inverse of f (mod q), and generating element F p which is an inverse of f (mod p); producing a public key that includes h, where h is congruent, mod q, to a product that can be derived using g and F q ; producing a private key from which f and F p can be derived; producing an encoded message e by encoding the message m using the public key and a random element .o slashed.; and producing a decoded message by decoding the encoded message e using the private key.

Claim 3

Dependent Claim 18 words

The method as defined by claim 1, wherein said ring R is a module over a ring Z.

Claim 4

Dependent Claim 25 words

The method as defined by claim 1, wherein the dimension of R over Z is N, and where N is an integer greater than 1.

Claim 5

Dependent Claim 20 words

The method as defined by claim 3, wherein the ring R is a ring of polynomials modulo a particular polynomial.

Claim 6

Dependent Claim 40 words

The method as defined by claim 1, wherein said step of generating elements further comprises generating element G q which is an inverse of g (mod q), and generating element G p which is an inverse of g (mod p).

Claim 7

Dependent Claim 32 words

The method as defined by claim 5, wherein said element G q is used in the derivation of said public key and said element G p is part of said private key.

Claim 8

Dependent Claim 51 words

The method as defined by claim 1, wherein said selecting step further includes selecting a positive integer K, and wherein said element g comprises respective g i , with i=1,2, . . . ,K, and wherein said public key, h, comprises respective h i , with i=1,2, . . . K.

Claim 9

Dependent Claim 37 words

The method as defined by claim 7, wherein said random element .o slashed. comprises respective .o slashed. i in the ideal p, with i=1,2, . . . ,K, and wherein said encoded message is produced as ##EQU13##

Claim 10

Dependent Claim 19 words

The method as defined by claim 1, wherein said public and private keys each further include p and q.

Claim 11

Dependent Claim 19 words

The method as defined by claim 1, wherein said ideals p and q are generated by relatively prime integers.

Claim 12

Dependent Claim 31 words

The method as defined by claim 10, wherein the encoded message is congruent, mod q, to the sum of the message m and a product that includes .o slashed. and h.

Claim 13

Dependent Claim 24 words

The method as defined by claim 10, wherein said integers p and q are unequal and both p and q are greater than 1.

Claim 14

Dependent Claim 36 words

The method as defined by claim 1, wherein said encoded message is produced by a user at one location, transmitted from said one location to another location, and decoded by a user at said another location.

Claim 15

Independent Claim 104 words

A method for encoding and decoding a digital message m, comprising the steps of: selecting integers p and q; generating polynomials f and g; determining inverses F q and F p , where F.sub.q *f≡1(mod q) F.sub.p *f≡1(mod p); producing a public key that includes p, q, h, where h≡F.sub.q *g(mod q); producing a private key that includes f and F p ; producing an encoded message e by encoding the message m in the form of a polynomial using the public key and a random polynomial .o slashed.; and producing a decoded message by decoding the encoded message e using the private key.

Claim 16

Independent Claim 104 words

A method for encoding and decoding a digital message m, comprising the steps of: selecting integers p and q; generating polynomials f and g; determining inverses F q and F p , where F.sub.q *f≡1(mod q) F.sub.p *f≡1(mod p); producing a public key that includes p, q, h, where h≡F.sub.q *g(mod q); producing a private key that includes f and F p ; producing an encoded message e by encoding the message m in the form of a polynomial using the public key and a random polynomial .o slashed.; and producing a decoded message by decoding the encoded message e using the private key.

Claim 17

Dependent Claim 18 words

The method as defined by claim 14, wherein said encoded message e is produced as e≡p.o slashed.*h+m(mod q).

Claim 18

Dependent Claim 28 words

The method as defined by claim 15, wherein said decoded message is produced by computing a≡f*e(mod q), and then computing the decoded message, m', as m'≡F.sub.p *a(mod p).

Claim 19

Dependent Claim 69 words

The method as defined by claim 14, wherein said step of generating polynomials f and g includes selecting a positive integer K and generating K polynomials g, as g 1 , g 2 , . . . ,g K , and wherein said public key comprises h i , h 2 , . . . ,h K , where h.sub.i F.sub.q *g.sub.i (mod q), i=1,2, . . . ,K.

Claim 20

Dependent Claim 48 words

The method as defined by claim 17, wherein said encoded message e is produced as e≡p.o slashed..sub.1 *h.sub.1 +p.o slashed..sub.2 *h.sub.2 + . . . +p.o slashed..sub.K *h.sub.K +m(mod q) where .o slashed. 1 ,.o slashed. 2 , . . . ,.o slashed. K are K random polynomials.

Claim 21

Dependent Claim 36 words

The method as defined by claim 14, wherein said encoded message is produced by a user at one location, transmitted from said one location to another location, and decoded by a user at said another location.

Claim 22

Dependent Claim 39 words

The method as defined by claim 14, wherein a monic polynomial M(X) is selected and multiplication of polynomials is accomplished by first performing ordinary multiplication of polynomials and then dividing the result by M(X) and retaining only the remainder.

Claim 23

Dependent Claim 25 words

The method as defined by claim 14, wherein a non-zero integer N is selected and multiplication of polynomials is accomplished by reducing exponents modulo N.

Claim 24

Dependent Claim 22 words

The method as defined by claim 14, wherein said polynomials f, g, m and .o slashed. are constrained to have bounded coefficients.

Claim 25

Dependent Claim 51 words

The method as defined by claim 22, wherein said integer q is chosen smaller than a quantity determined by the said integer p, the degrees of the said polynomials f, g, m and .o slashed., and the said constraints on the coefficients of the said f, g, m and .o slashed..

Claim 26

Dependent Claim 52 words

The method as defined by claim 22, wherein said integer q is chosen larger than a quantity determined by the said integer p, the degrees of the said polynomials f, g, m and .o slashed., and the said constraints on the coefficients of the said polynomials f, g, m and .o slashed..

Claim 27

Independent Claim 225 words

A method for encoding and decoding a digital message, comprising the steps of: selecting relatively prime integers p and q; selecting a non-zero integer K; producing K+2 matrices, f,g,w 1 ,w 2 , . . . w K from a ring of matrices with integer coefficients, with w i ≡0 (mod p) for i=1,2, . . . ,K, producing inverse matrices F p , F q , G p and G q , from said ring of matrices where fF p ≡I (mod p) fF q ≡I (mod q) gG p ≡I (mod p) gG q ≡I (mod q) where I is an identity matrix; producing a public key as a list of K matrices (h 1 ,h 2 , . . . h K ) where h.sub.i ≡F.sub.q w.sub.i G.sub.q (mod q), i=1,2, . . . ,K; producing a private key as the matrices (f, g, F p , G p ); producing an encoded message e by encoding the message m using the private key and random integers .o slashed. 1 , .o slashed. 2 , . . . ,.o slashed. K as e≡.o slashed..sub.1 h.sub.1 +.o slashed..sub.2 h.sub.2 + . . . +.o slashed..sub.K h.sub.K +m(mod q); and producing a decoded message m' by computing a≡feg(mod q) and b≡a(mod p) and then computing the decoded message m' as m'≡F.sub.p bG.sub.p (mod p).

Claim 28

Independent Claim 225 words

A method for encoding and decoding a digital message, comprising the steps of: selecting relatively prime integers p and q; selecting a non-zero integer K; producing K+2 matrices, f,g,w 1 ,w 2 , . . . w K from a ring of matrices with integer coefficients, with w i ≡0 (mod p) for i=1,2, . . . ,K, producing inverse matrices F p , F q , G p and G q , from said ring of matrices where fF p ≡I (mod p) fF q ≡I (mod q) gG p ≡I (mod p) gG q ≡I (mod q) where I is an identity matrix; producing a public key as a list of K matrices (h 1 ,h 2 , . . . h K ) where h.sub.i ≡F.sub.q w.sub.i G.sub.q (mod q), i=1,2, . . . ,K; producing a private key as the matrices (f, g, F p , G p ); producing an encoded message e by encoding the message m using the private key and random integers .o slashed. 1 , .o slashed. 2 , . . . ,.o slashed. K as e≡.o slashed..sub.1 h.sub.1 +.o slashed..sub.2 h.sub.2 + . . . +.o slashed..sub.K h.sub.K +m(mod q); and producing a decoded message m' by computing a≡feg(mod q) and b≡a(mod p) and then computing the decoded message m' as m'≡F.sub.p bG.sub.p (mod p).

Claim 29

Dependent Claim 36 words

The method as defined by claim 25, wherein said encoded message is produced by a user at one location, transmitted from said one location to another location, and decoded by a user at said another location.

Claim 30

Dependent Claim 54 words

The method as defined by claim 25, wherein said matrices w 1 , w 2 , . . . w K , f, g, and m are constrained to have bounded coefficients and the integers .o slashed. 1 , .o slashed. 2 , . . . ,.o slashed. K are constrained to be bounded.

Claim 31

Dependent Claim 88 words

The method as defined by claim 27, wherein said integer q is chosen smaller than a quantity determined by said integer p, said integer K, the degrees of said polynomials w 1 ,w 2 , . . . ,w K , f, g, and m, said constraints on the coefficients of said polynomials w 1 ,w 2 , . . . w K , f, g, and m, and said constraints on the integers .o slashed. 1 ,.o slashed. 2 , . . . .o slashed. K .

Claim 32

Dependent Claim 89 words

The method as defined by claim 27, wherein said integer q is chosen larger than a quantity determined by said integer p, said integer K, the degrees of said polynomials w 1 ,w 2 , . . . , w K , f, g, and m, said constraints on the coefficients of said polynomials w 1 ,w 2 , . . . ,w K , f, g, and m, and said constraints on the integers .o slashed. 1 ,.o slashed. 2 , . . . .o slashed. K .

Claim 33

Independent Claim 137 words

A system for encoding and decoding a digital message m, comprising: means for selecting ideals p and q; means for generating elements f and g of a ring R, and generating element F q which is an inverse of f (mod q), and generating element F p which is an inverse of f (mod p); means for producing a public key that includes h, where h is congruent, mod q, to a product that can be derived using g and F q ; means for producing a private key from which f and F p can be derived; means for producing an encoded message e by encoding the message m using the public key and a random element .o slashed.; and means for producing a decoded message by decoding the encoded message e using the private key.

Claim 34

Independent Claim 137 words

A system for encoding and decoding a digital message m, comprising: means for selecting ideals p and q; means for generating elements f and g of a ring R, and generating element F q which is an inverse of f (mod q), and generating element F p which is an inverse of f (mod p); means for producing a public key that includes h, where h is congruent, mod q, to a product that can be derived using g and F q ; means for producing a private key from which f and F p can be derived; means for producing an encoded message e by encoding the message m using the public key and a random element .o slashed.; and means for producing a decoded message by decoding the encoded message e using the private key.

Claim 35

Dependent Claim 36 words

The system as defined by claim 30, wherein said encoded message is produced by a user at one location, transmitted from said one location to another location, and decoded by a user at said another location.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-06-27	2003-12-27	2004-06-27	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-06-27	2007-12-27	2008-06-27	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-06-27	2011-12-27	2012-06-27	$7700.00	Window Closed / Lapsed

Public key cryptosystem method and apparatus

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag