US4935962A — Method and system for authentication

Claim 1

Independent Claim 111 words

A method for preparing an entity to be authenticated by an authenticating device including: selecting a modulus N which is a product of two or more prime numbers; selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; determining an integer d such that e·d =1 (mod Φ(N)); selecting a set of n public factors F 1 , . . . , F n , 0<F i <N; calculating S i =F i d (mod N) for i=1, . . , n; and storing the n values S i , i=1, . . . , n, and the value N in said entity.

Claim 2

Independent Claim 111 words

A method for preparing an entity to be authenticated by an authenticating device including: selecting a modulus N which is a product of two or more prime numbers; selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; determining an integer d such that e·d =1 (mod Φ(N)); selecting a set of n public factors F 1 , . . . , F n , 0<F i <N; calculating S i =F i d (mod N) for i=1, . . , n; and storing the n values S i , i=1, . . . , n, and the value N in said entity.

Claim 3

Dependent Claim 25 words

A method according to claim 1 wherein said entity includes a PROM, said method further comprising: storing said n values S i in said PROM.

Claim 4

Dependent Claim 17 words

A method according to claim 2 further comprising: providing said entity with processing means and input/output means.

Claim 5

Dependent Claim 34 words

A method according to claim 1 further comprising: assigning a public factor F ID unique to said entity; computing S ID=F ID d (mod N); and storing the value S ID in said entity.

Claim 6

Independent Claim 187 words

A method of authenticating an entity by an authentication device comprising: (a) selecting a modulus N which is a product of two or more prime numbers; (b) selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; (c) determining an integer d such that e·d=1 (mod Φ(N)); (d) selecting a set of n public factors F 1 , . . . , F n , 0<F i <N; (e) calculating S i =F i d (mod N) for i=1, . . . , n; (f) storing the n values S i , i=1, . . . , n), and the value N in said entity; (g) placing said entity in communication with said authentication device; (h) generating in said authentication device an n bit binary string v=v i (i=1, . . . , n); (i) transmitting said binary string v to said entity; (h) calculating in said entity ##EQU22## (k) transmitting Y to said authentication device; (l) calculating in said authentication device: X ref ##EQU23## and X.sub.act =Y.sup.e (mod N); and (m) comparing X ref and X act .

Claim 7

Independent Claim 187 words

A method of authenticating an entity by an authentication device comprising: (a) selecting a modulus N which is a product of two or more prime numbers; (b) selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; (c) determining an integer d such that e·d=1 (mod Φ(N)); (d) selecting a set of n public factors F 1 , . . . , F n , 0<F i <N; (e) calculating S i =F i d (mod N) for i=1, . . . , n; (f) storing the n values S i , i=1, . . . , n), and the value N in said entity; (g) placing said entity in communication with said authentication device; (h) generating in said authentication device an n bit binary string v=v i (i=1, . . . , n); (i) transmitting said binary string v to said entity; (h) calculating in said entity ##EQU22## (k) transmitting Y to said authentication device; (l) calculating in said authentication device: X ref ##EQU23## and X.sub.act =Y.sup.e (mod N); and (m) comparing X ref and X act .

Claim 8

Dependent Claim 70 words

A method according to claim 5, wherein in said step (j) the value of Y is calculated utilizing selectively an additional predetermined factor S p , such that the total number of factors included in the calculation of Y is even, and wherein in said step (1), the value of X ref is correspondingly calculated. utilizing selectively an additional factor F p , where S p =F p d .

Claim 9

Dependent Claim 34 words

A method according to claim 5 further comprising: storing said said public factors F 1 , . . . , F n , and the values of N and e in said authentication device.

Claim 10

Dependent Claim 23 words

A method according to claim 7 further comprising: repeating said steps (h) to (m) a plurality of times, using random values of v.

Claim 11

Independent Claim 151 words

A method of certifying a message M by an entity comprising: selecting a modulus N which is a product of two or more prime numbers; selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; determining an integer d such that e·d=1 (mod Φ(N)); selecting a set of n public factors F 1 , . . . , F n , 0<F i<N; calculating S i=F i d (mod N) for i=1, . . . , n; storing the n values S i , i=1, . . . , n, and the value N in said entity computing a change sensitive transformation H of said message M; generating an n bit binary string v=v i , i=1, . . . , n, using the computed value of H; computing ##EQU24## and appending Y as a message authentication code certificate to said message M.

Claim 12

Independent Claim 151 words

A method of certifying a message M by an entity comprising: selecting a modulus N which is a product of two or more prime numbers; selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; determining an integer d such that e·d=1 (mod Φ(N)); selecting a set of n public factors F 1 , . . . , F n , 0<F i<N; calculating S i=F i d (mod N) for i=1, . . . , n; storing the n values S i , i=1, . . . , n, and the value N in said entity computing a change sensitive transformation H of said message M; generating an n bit binary string v=v i , i=1, . . . , n, using the computed value of H; computing ##EQU24## and appending Y as a message authentication code certificate to said message M.

Claim 13

Dependent Claim 48 words

A method according to claim 9 wherein said step of generating an n bit binary string v includes: converting H to a binary value J; segmenting J into subfields of length n; and adding together the individual subfields modulo 2 to for said n bit binary string v.

Claim 14

Dependent Claim 21 words

A method according to claim 9 wherein said step of computing a change sensitive transformation H includes: computing H=M.sup.e (mod N).

Claim 15

Dependent Claim 48 words

A method according to claim 11 wherein said step of generating an n bit binary string v includes: converting H to a binary value J; segmenting J into subfields of length n; and adding together the individual subfields modulo 2 to form said n bit binary string v.

Claim 16

Independent Claim 208 words

A method of authenticating an entity by an authentication device comprising: (a) selecting a modulus N which is a product of two or more prime numbers; (b) selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; (c) determining an integer d such that e·d=1 (mod Φ(N)); (d) selecting a set of n public factors F 1 , . . . , F n , 0<F i <N; (e) calculating S i=F i d (mod N) for i=1, . . . , n; (f) storing the n values S i , i=1, . . . , n, and the value N in said entity; (g) placing said entity in communication with said authentication device; (h) generating in said authentication device an n bit binary string v=v i , i=1, . . . , n; (i) transmitting said binary string v to said entity; (j) selecting a value S set in said entity and computing in said entity F set =S set e ; (k) calculating in said entity ##EQU25## (l) transmitting Y and F set to said authentication device; (m) calculating in said authentication device: ##EQU26## and X.sub.act =Y.sup.e (mod N); and (n) comparing X ref and X act .

Claim 17

Independent Claim 208 words

A method of authenticating an entity by an authentication device comprising: (a) selecting a modulus N which is a product of two or more prime numbers; (b) selecting an integer e which is relatively prime to Φ(N), where Φ(N) is Euler's totient function of N; (c) determining an integer d such that e·d=1 (mod Φ(N)); (d) selecting a set of n public factors F 1 , . . . , F n , 0<F i <N; (e) calculating S i=F i d (mod N) for i=1, . . . , n; (f) storing the n values S i , i=1, . . . , n, and the value N in said entity; (g) placing said entity in communication with said authentication device; (h) generating in said authentication device an n bit binary string v=v i , i=1, . . . , n; (i) transmitting said binary string v to said entity; (j) selecting a value S set in said entity and computing in said entity F set =S set e ; (k) calculating in said entity ##EQU25## (l) transmitting Y and F set to said authentication device; (m) calculating in said authentication device: ##EQU26## and X.sub.act =Y.sup.e (mod N); and (n) comparing X ref and X act .

Claim 18

Dependent Claim 24 words

A method according to claim 13 wherein S set is selected in accordance with a count value which is incremented for each Y calculation.

Claim 19

Dependent Claim 98 words

A method according to claim 14 wherein S set is determined by selecting a set S si of said factors S i , said selection being in accordance with a binary string V s =v si generated in said entity, and wherein Y is calculated according to the formula: ##EQU27## where the v ai values correspond to the bits of said n-bit binary string generated in said authentication device; wherein step (1) further comprises transmitting V s to said authentication device; and wherein, in step (m), the value of X ref is calculated according to the formula: ##EQU28##

Claim 20

Independent Claim 112 words

A system, including an entity for generating an output Y in response to an input v, said entity comprising: memory means having stored therein a modulus N which is the product of at least two prime numbers, and a set of n factors S i , i=1, . . . , n, where S i =F i d (mod N), wherein d is the secret key counterpart of a public key e associated with the modulus N, and F i , i=1, . . . , n, are n public factors, 0<F i <N; processing means adapted to compute ##EQU29## where v=v i is an n bit binary string; and input/output means.

Claim 21

Independent Claim 112 words

A system, including an entity for generating an output Y in response to an input v, said entity comprising: memory means having stored therein a modulus N which is the product of at least two prime numbers, and a set of n factors S i , i=1, . . . , n, where S i =F i d (mod N), wherein d is the secret key counterpart of a public key e associated with the modulus N, and F i , i=1, . . . , n, are n public factors, 0<F i <N; processing means adapted to compute ##EQU29## where v=v i is an n bit binary string; and input/output means.

Claim 22

Dependent Claim 31 words

A system according to claim 16, wherein the value of Y includes an additional factor S set which is dependent on a count value which is incremented for each Y calculation.

Claim 23

Dependent Claim 62 words

A system according to claim 17, wherein said memory means has stored therein an additional parity factor S p , and wherein said processing means is adapted to compute the value of Y by selectively including said additional parity factor S p in the expression for Y, such that the total members of factors included in the calculation of Y is even.

Claim 24

Dependent Claim 89 words

A system according to claim 16 wherein: said memory means has stored therein the value of said public key e; and said processing means is further adapted (a) to compute H=M e (mod N), where M is a message to be transmitted by said entity; (b) to convert H to a binary n bit vector v; and (c) to compute ##EQU30## using the bits v i of the computed vector v; and said input/output means is adapted to transmit Y as a message authentication code associated with said message.

Claim 25

Dependent Claim 79 words

A system according to claim 19, further including an authentication device which comprises: further input/output means; further memory means having stored therein said n public factors F i (i=1, . . . , n), said modulus N, and said public key e; and further processing means adapted to compute ##EQU31## (mod N); and X act =Y 3 (mod N) using the stored values of F i , N and e, and to compare X ref with X act .

Claim 26

Dependent Claim 36 words

A system according to claim 16, wherein said memory means has stored therein a public factor F ID unique to said entity, and a value S ID , where S ID =F ID d (mod N).

Claim 27

Dependent Claim 78 words

A system according to claim 21, further including an authentication device which comprises: further input/output means; further memory means having stored therein said n public factors F i 1 , . . . , n, said modulus N, and said public key e; and further processing means adapted to compute ##EQU32## and X act =Y e (mod N) using the stored values of F i , N and e, and to compare X ref with X act .

Claim 28

Dependent Claim 17 words

A system according to claim 22 wherein said further processing means is further adapted to compute ##EQU33##

Claim 29

Dependent Claim 78 words

A system according to claim 16, further including an authentication device which comprises: further input/output means; further memory means having stored therein said n public factors F i , i=1, . . . , n, said modulus N, and said public key e; and further processing means adapted to compute ##EQU34## and X act =Y e (mod N) using the stored values of F i , N and e, and to compare X ref with X act .

Claim 30

Dependent Claim 155 words

An entity comprising: memory means having stored therein (a) a modulus N which is the product of at least two prime numbers, (b) a set of n factors S i , i=1, . . . , n, where S i =F i .sup. (mod N), wherein d is the secret key counterpart of a public key e associated with the modulus N, and F i , i=1, . . . , n, are n public factors 0<F i <N, (c) said n public factors F i , i=1, . . . , n, (d) said modulus N, and (e) said public key e; processing means adapted to compute Y ##EQU35## where v=v i is an n bit binary string and further adapted to compute ##EQU36## and X act =Y e (mod N) using the stored values of F i , N and e, and to compare X ref with X act ; and input/output means.

Claim 31

Dependent Claim 155 words

An entity comprising: memory means having stored therein (a) a modulus N which is the product of at least two prime numbers, (b) a set of n factors S i , i=1, . . . , n, where S i =F i .sup. (mod N), wherein d is the secret key counterpart of a public key e associated with the modulus N, and F i , i=1, . . . , n, are n public factors 0<F i <N, (c) said n public factors F i , i=1, . . . , n, (d) said modulus N, and (e) said public key e; processing means adapted to compute Y ##EQU35## where v=v i is an n bit binary string and further adapted to compute ##EQU36## and X act =Y e (mod N) using the stored values of F i , N and e, and to compare X ref with X act ; and input/output means.

Claim 32

Dependent Claim 88 words

An entity according to claim 25 wherein: said memory means has stored therein the value of said public key e; said processing means is further adapted (a) to compute H=M e (mod N), where M is a message to be transmitted by said entity; (b) to convert H to a binary n bit vector v; and (c) to compute ##EQU37## using the bits v i of the computed vector v; and said input/output means is adapted to transmit Y as a message authentication code associated with said message.

Claim 33

Dependent Claim 36 words

An entity according to claim 26, wherein said memory means has stored therein a public factor F ID unique to said entity, and a value S ID , where S ID =F ID d (mod N).

Claim 34

Dependent Claim 16 words

An entity according to claim 27 wherein said processing means is further adapted to compute ##EQU38##

Claim 35

Dependent Claim 17 words

An entity according to claim 28 wherein said processing means is further adapted to compute ##EQU39## .

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1993-06-18	1993-12-18	1994-06-19	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1997-06-18	1997-12-18	1998-06-19	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2001-06-18	2001-12-18	2002-06-19	$7700.00	Window Closed / Lapsed

Method and system for authentication

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag