United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,680,460
`
`Tomko et al.
`
`[45] Date of Patent:
`
`*Oct. 21, 1997
`
`USOOS680460A
`
`[54] BIOMETRIC CONTROLLED KEY
`GENERATION
`
`[75]
`
`Inventors: George J. Tomko, East York; Colin
`Soutar; Gregory J. Schmidt, both of
`Toronto, all of Canada
`
`[73] Assignce: Mytec Technologies, Inc., Don Mills,
`Canada
`
`[*] Notice:
`
`The term of this patent shall not extend
`beyond the expiration date of Pat. No.
`5,541,994.
`
`[21] Appl. No.: 512,491
`
`[22] Filed:
`
`Aug. 8, 1995
`
`Related U.S. Application Data
`
`[63] Continuation-impart of Ser. No. 301,677, Sep. 7, 1994, Pat.
`No. 5,541,994.
`
`Int. C16 ....................................................... HMK 9/00
`[51]
`[52] U.S. Cl.
`................................... 380/23; 380/25; 380/4;
`380/30
`
`[58] Field of Search ............................... 380/3, 4, 23, 25,
`380/30
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`.
`
`.
`
`364/822
`
`11/1973 McMahon ........................ 340/1463 E
`3,771,129
`7/1985 Ruell .
`4,532,508
`6/1989 Owechko .................................. 382/31
`4,837,843
`10/1989 Tomko.
`4,876,725
`2/1991 Piosenka et a1.
`4,993,068
`8/1991 Homer
`5,040,140
`9/1991 Marsh et a1.
`5,050,220
`3/1992 Barbanell
`........ 235/379
`5,095,194
`
`8/1992 Barbanell
`359/2
`5,138,468
`9/1992 Takfifle fit 81 -
`359/7
`5,150,229
`5,159,474 “”1992 Fluke 9‘ 31-
`------ 359/29
`5,245,329
`9/1993 6°11wa """"
`340/825'31
`5,268,963
`12/1993 Monroe et al.
`.
`...... 380/23
`5,230,527
`1/1994 Gullmanetal.
`.. 330/23
`5,327,286
`711994 Sampsell eta].
`359/561
`5,343,415
`3/1994 Itoh et al.
`...........
`364/725
`
`.
`9/1994 Lynn et a1.
`5,345,508
`9/1994 Saito eta]. .................................. 359/9
`5,347,375
`1/1995 Itoh et al.
`..
`. 364/822
`5,386,378
`
`5/1995 Simon et a1.
`. 250/550
`..
`5,418,380
`6/1995 Indeck et al.
`............................... 380/4
`5,428,683
`5,469,506 11/1995 Berson et a1.
`.
`5,541,994
`7/1996 Tomko et a1.
`
`............................ 380/30
`
`FOREIGN PATENT DOCUMENTS
`GOGF 3/06
`0 396 774
`11/1990 European Pat. Ofl’.
`..
`
`2 360 079 10/1985 Germany ......................... 609C 1/00
`4243908
`6/1994 Germany .
`2 132 857
`7/1984 United Kingdom ............. H04K 1/00
`
`OTHER PUBLICATIONS
`
`“Novel Applications of Cryptography in Digital Communi—
`cations”, Jim K. Omura, IEEE Communications Magazine,
`vol. 28, 1990, pp. 21—29.
`“The Mathematics of Public—Key Cryptography”, Martin E.
`Hellman, Scientific American Aug. 1979, pp. 146 to 157.
`
`Primary Examiner—David C. Cain
`Attorney, Agent, or Firm—Merchant, Gould, Smith, Edell,
`Welter & Schmidt, BA.
`
`[57]
`
`ABSTRACT
`
`A key generation system is implemented as follows. In an
`enrolment apparatus, a unique number for use with PIN
`operated machines or public key cryptography systems is
`generated by manipulation of fingerprint information of a
`subscriber. Afilter is then generated which is a function both
`of the Fourier transform of the subscriber’s fingerprint(s)
`and of the unique number. This filter is stored on a subscriber
`card. When the subscriber wishes to generate his key, he
`inputs his card to a card reader of an apparatus and places his
`finger(s) on a fingerprint input. The apparatus generates an
`optical Fourier transform from the fingerprint input. The
`Fourier transform signal is incident on to a spatial light
`modulator programmed with the filter information from the
`card. An inverse transform is generated from the filtered
`signal and this is used to regenerate the key that will be used
`as the PIN in a PIN operated device, or as the private key
`to
`h S stem.
`‘13? gmp 5’ y
`
`55 Claims, 4 Drawing Sheets
`
`
`
`
`75
`74
`7o
`95
`
`77
`PUBLIC
`_1
`
`79E
`CORRELATOR142
`“gala
`
`
`iNPUT
`“is 14s ‘44 146
`
`
`MESSAGE
`
`STORE
`
`Ba
`
`
`DESCRIPTION/
`RANDOM
`PRIVATE!
`
`ENCRVFTION
`NUMBER
`PUBLIC KEY
`SYSTEM
`
`I GENERATORI GENERATOR KEY
`
`82
`
`94
`OUTPUT
`
`MESSAGE
`
`STORE
` Punuc KEY
`COMMUNICATOR
`
`
`
`
`
`
`Apple 1025
`Apple 1025
`Apple v. USR
`Apple v. USR
`IPR2018-00810
`|PR2018-00810
`
`

`

`US. Patent
`
`Oct. 21, 1997
`
`Sheet 1 of 4
`
`5,680,460
`
`EV
`
`MEG—z:
`
`mmmEDZ
`
`mOhémsz
`
`N¢
`
`NN
`
`ON
`
`mmwb
`
`szEmo
`
`z_n_
`
`om
`
`FGE
`
`mv
`
`MDQZD
`
`mmkdu
`
`mOhéme—O
`
`mm
`
`mm
`
`
`
`

`

`US. Patent
`
`Oct. 21, 1997
`
`Sheet 2 of 4
`
`5,680,460
`
`Famz_
`
`w0<wwm§
`
`mmOHw
`
`8m3mi3:m3
`
`mm
`
`Eamomm2ExNEmotqdmmoo02.5:;OR8.E.OE
`
`mmmmvm82n28Em:N:
`
`m35/
`
`mo<mwm2
`
`«522232.200
`
`
`
`02ON-#55ExOsman.o9\\1
`
`SE2054
`
`
`
` 5F4e>55%$2«.025szmobémzmomm?A'v
`
`.QOmNmA'v
`
`N.OE
`
`
`
`
`
`
`
`
`
`
`
`295.580EEEE282%
`
`zoEEozmEx03%;mmmsSzmewwmoomn.0.:
`
`
`
`
`

`

`US. Patent
`
`Oct. 21, 1997
`
`Sheet 3 of 4
`
`5,680,460
`
`om
`
`mOwwmoomm
`
` ZOFOMIE
` mOFUMFMQ
`
`,m.9...
`
`ZO_._.<._mmmOo
`
`mz<4m
`
`Oz_zz<ow
`
`

`

`U
`
`a
`
`4
`
`4
`
`5,680,460 ,
`
`P\S.Em
`
`
`
`m9:\mi3;m:mE:
`
`mmix\E
`
`
`
`12..mm:mm?!a.
`.51I0_l_.vé!\/I‘_'.I
`
`
`
` SShawnamemmmoomn..mm.25JmomEm,8m39:N3
`
`
`
`
`
`am>
`
`E
`
`mmeanatalv
`
`aIg_,1"E4
`
`
`

`

`1
`BIOMETRIC CONTROLLED KEY
`GENERATION
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation in part of application
`Ser. No. 08/301,677 filed Sep. 7, 1994 now US. Pat. No.
`5,541,994.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`This invention relates to a system for generating a key
`under the control of a biometric, such as a fingerprint The
`system has application in a public key cryptographic system
`and for devices requiring a personal identification number
`(PIN) for operation.
`2. Description of the Related Art
`In a public key cryptosystem, a plain text message may be
`encrypted by inputting the message and an enciphering key
`to an encryption algorithm To decipher the message, the
`encrypted message is input to the inverse of the same
`algorithm along with a deciphering key. As with many
`encryption techniques,
`the encryption algorithm efiects
`transformations of the plain text message which are so
`complicated it is computationally infeasible to reverse the
`process even if the algorithm is known. A peculiarity of
`public key systems is that it is also computationally infea-
`sible to determine the deciphering key from the enciphering
`key. Consequently, in a public key cryptosystem, both the
`algorithm and the enciphering key may be made available to
`the public without jeopardising the security of a message
`enciphered with the enciphering key. Hence the term “public
`key” for the enciphering key. The deciphering key, which is
`confidential, is known as a “private key”. With a public key
`system, anyone who wishes to receive encrypted messages
`may make an encryption algorithm and a public key freely
`available. Moreover, some public key systems allow the
`transmission of a “digital signature” that prevents forgery of
`messages by a receiver as well as a third party.
`By way of example, with the known “knapsack”
`cryptosystem, a public key is derived from a private key
`utilising modular arithmetic. Each element in the array
`(vector) forming a private key is multiplied by a large prime
`number, x, and divided by a second large prime number, y.
`The corresponding element of the public key vector is the
`remainder from this operation. In order to encrypt a plain
`test message, the message is digitised and the digital string
`grouped into arrays (vectors) each having the same number
`of elements as the number of elements in the array which
`comprises the public key. The encrypted message is formed
`from the vector dot product of the public key vector with
`each vector formed from the digifised plain text message.
`Clearly the exemplary encryption technique and the tech—
`nique for deriving a public key from a private key make it
`computationally infeasible to determine either the private
`key of the plain text message even though the algorithm,
`along with the encrypted text, is known. There are, however,
`known techniques for structuring a private key vector such
`that, with it, the plain text can be rapidly derived from an
`encrypted message. Two sample techniques in this regard
`are described in an article entitled "The Mathematics of
`Public-Key Cryptography” Scientific American August
`1979, pages 146 to 157.
`The problem with such public key cryptograph systems is
`that, in use, they require a secure, yet readily available,
`
`5,680,460
`
`2
`
`private key. The private key has to either be remembered,
`which is not practical, or stored in a secure place and
`retrieved The security of storage therefore is at best depen-
`dent on password access which itself can be compromised.
`A number of devices, such as automated teller machines
`(A'I‘Ms) and symmetric encryption/decryption systems,
`require the entry of a PIN for operation. A PIN therefore acts
`a private key which permits operation of such devices.
`Devices requiring a data key for operation share the same
`problem as identified for public key cryptographic systems:
`the data key must be secure and yet readily available. To
`mitigate this problem, PIN operated devices often utilize a
`short key which may be memorized by the user. However,
`not all users do memorize their PIN and, in any event, use
`of a short PIN reduces the security of the PIN operated
`device.
`
`This invention seeks to overcome drawbacks of the
`
`10
`
`15'
`
`known prior art and provide an extremely secure private key
`which is not even known by the user yet is readily acces-
`sible.
`
`20
`
`SUMMARY OF THE INVENTION
`
`25
`
`3O
`
`35
`
`45
`
`50
`
`According to the present invention, there is provided a.
`biometric controlled key generation system, comprising: a
`body part input for generating an optical information signal
`impressed with a biometric; Fourier transform means along
`a path of said optical information signal to obtain a Fourier
`transform representation of said information signal; a pro-
`grammable filter responsive to said Fourier transform means
`for, filtering said Fourier transform representation of said
`information signal to obtain a filtered Fourier transform
`representation; means for reading data from a data carrier
`storing filter information and for programming said pro—
`grammable filter with said filter information data; inverse
`transform means responsive to said filter to inverse Fourier
`transform said filtered Fomier transform representation to
`obtain an inverse transform representation; key generating
`means responsive to said inverse transform means for gen-
`erating a private key.
`According to another aspect of this invention, there is
`provided a method for generating a private key, comprising
`the steps of: generating an optical
`information signal
`impressed with a biometric; obtaining a Fourier transform
`representation of said information signal; receiving a filter
`and filtering said Fourier transform representation; informa—
`tion signal with said filter to obtain a filtered Fourier
`transform representation; obtaining an inverse Fourier trans-
`form representation of said filtered Fourier transform rep-
`resentation; generating a private key from said inverse
`transform representation.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`In the figures which disclose example embodiments of the
`invention,
`
`55
`
`FIG. 1 is a schematic diagram of an enrolment apparatus
`made in accordance with this invention,
`FIG. 2 is a schematic diagram of an encrypting/decrypting
`apparatus made in accordance with this invention,
`FIG. 3 is a schematic diagram of a portion of FIG. 2, and
`FIG. 4 is a schematic diagram of a PIN generating
`apparatus made in accordance with this invention.
`DESCRIPTION OF THE PREFERRED
`EMBODIIVIENTS
`
`65
`
`In the following, lower case letters represent functions in
`the “spatial domain” and upper case letters represent the
`
`

`

`5,680,460
`
`3
`“Fourier transformed frequency domain”. Also, we use the
`following terminology: “Fourier transform” denotes a trans-
`formation from the spatial domain to the frequency domain,
`and “inverse Fourier transform” denotes a transformation
`from the frequency domain to the spatial domain. It should
`be noted that when the inverse Fourier transform is imple-
`mented optically (using a lens), the transformation is in fact
`equivalent to the Fourier transform. The consequence of this
`is that a coordinate reversal occurs in the resulting, spatial
`domain. On the other hand, digital implementation of the
`inverse Fourier transform can be accomplished as math-
`ematically defined, and so no such coordinate reversal
`occurs. However, both (optical and digital) implementations
`of the inverse Fourier transform can be used to produce the
`correlation operation which is required for this invention.
`An individual who wishes to use the encrypting and
`decrypting apparatus of this invention is enroled by way of
`enrolment apparatus 10 of FIG. 1. With reference to FIG. 1,
`enrolment apparatus 10 comprises an input system 29 with
`a light source 30, which may be a coherent source, an
`expander lens 31, and a collimator lens 33 to illuminate a
`prism 35 with a beam 37. One face of the prism forms an
`input screen 28. The individual to be enroled places a finger
`(or fingers) 12 on the input screen. The input system utilized
`the principle of total internal reflection to read the pattern
`formed by the furrows of the input fingerprint pattern. That
`is, a furrow will create an air space over the surface of a glass
`screen, allowing light which is internally reflected from the
`interior surface of the screen to proceed unimpeded. Ridges,
`however, will be in contact with the surface, where they will
`scatter and absorb a portion of the illuminating light This
`effect is known as frustrated total internal reflection. In the
`result, the output beam 39 from the prism is an information
`beam carrying the fingerprint pattern, p. The optical beam 39
`inputs a lens 40 which images the fingerprint information
`onto an Image Capture and Digitizer Device ICDD, 41,
`comprising a light detector array, and AID converter and a
`processor. The ICDD converts the optical fingerprint infor-
`mation beam into a two-dimensional grey scale digital
`representation. The digital output 42 of the ICDD is input to
`a unique filter generator 43 and to a unique number genera-
`tor 44.
`
`The unique number generator 44 generates an array of
`numbers. This may be accomplished in any of a number of
`ways. For example, a Fourier transform of the fingerprint
`information may be calculated to obtain the Fomier trans-
`form co-eflicients of the transform. Selected ones of these
`Fourier transform co-efficients may then be chosen and
`combined to generate a number 11. It will be apparent that
`this number n is unique for any single placement of the
`particular fingerprint(s) on the input screen. Alternatively, u
`can be generated by a random number generator seeded with
`the selected Fourier transform co—efiicients. The unique
`number n is the used to generate an array of number g={g1,
`.
`.
`. gn} such that the values in the elements of g represent
`the unique number 11. For example, if u is a k—digit base 10
`number and if in any subsequent measurement of the values
`g1, .
`.
`. g", the detecting instrument will have a known error
`in detection which only allows [5 distinct values from O to
`m—l inclusive (m is the dynamic range of the detector), 11
`would be chosen to be the integer greater than or equal to
`logBlO". The unique number 11 can then be expanded into
`elements of g by using modulo division, i.e.:
`
`
`31 = Integer of 3""
`
`4
`—continued
`—1
`g, = Megs, ofHEEL30—2
`1
`-2
`g, = my, offlfiitL _ We, firm-{g
`
`etc. The array, g, is input to the unique filter generator 43.
`The unique filter generator 43 calculates the digital Fou-
`rier transform, P,‘ of the fingerprint information and gener—
`ates a two dimensional filter function, F, as follows. The
`mathematical multiplication of the fingerprint transform, P,
`with the filter, F, produces the two-dimensional light distri-
`bution S. F is generated so that the inverse Fourier transform
`of S, denoted by s, is equal to a series of n displaced
`delta-like functions 51, 82, .
`.
`. 5", where the square of the
`amplitude of 81 is equal to the corresponding value g1 in the
`array g. This may be represented mathematically by the
`following acts of equations which for convenience will be
`described in one dimension:
`Let
`
`p(x) be the input fingerprint pattern signal
`P(u) be the complex Fourier transform of the signal,
`denoted by |P(u)lexp(jq)(u)), where ¢(u) is the phase of
`the Fourier transform
`
`F(u) be the filter function
`and
`
`s(x) be the output signal
`We desire s(x) to have the following form:
`
`S(x)=d gr
`
`-5(Jr-Jn)+d 32
`
`'5(x-X2J+---q g»
`
`-8(x-xn)
`
`that is n delta functions at positions x1, x2, . . . x,, and relative
`intensities g1, g2, .
`.
`. g" respectively
`Then,
`
`Stu) = N g1
`
`~6<x—xx>-exp(—j2m)dx+
`
`-8(x—x2)~exp(—j21tux)dx+...
`N 32
`I..etx'=x—x1,x"=x~x2, etc.
`
`5(a) = N 31
`
`~6<x').exp(—izuuraa+xn)dx'+
`
`N 3; ~S(x")rflp(fi'21tu(x"+x2))dx"+...
`
`‘1 31 expat-run) 46(2) - expr—jzmuw +
`
`J 32
`
`~exp(—j21tux2) ~15(x")~exp(—j2m")dx"+. ..
`
`W -exp(-j21twc1)+\i? -=xp(—j2uuxz)+ . ..
`
`We require that
`
`P(U) ' F(u) = 5(a)
`
`_M
`P(u)
`
`Thus, F(u)
`That is,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`J 81
`
`'eXP(-J'2’Imxr)+
`
`65
`
`F“) =
`
`d g:
`
`'exp(-j27wz)+mq a. «am-firm")
`momma»
`
`

`

`5,680,460
`
`5
`
`_
`
`,
`=L§0fijfl -N gr
`
`—continued
`exp<~j2mm)+‘l g2
`
`expr—jznuxz)+...r
`
`In general |P(u)|=0 will occur for some values of u, resulting
`in singularities in the above expression for F(u). This
`problem is usually eliminated by imposing a magnitude
`constraint on F(u), such that
`
`6
`information, are transferred into the SLM 144 on line 79.
`The filter written on the SLM 144 modulates the finger-
`print’s optical transform through a multiplicative method
`which is part of the optical correlation operation which
`compares the subscribers fingerprint(s) with those repre-
`sented by the encoded filter F stored on the subscriber’s
`card. The output form the SLM 144 is an optical signal S‘
`, whose similarity to the transform function S depends on the
`
`S
`
`F04) =
`
`w - [ll g1
`
`exp(—j21tux1)+ q 32
`
`exp(—j21twq)+. . . ] for leu)! E 0:
`
`°XP(—j¢(“)) ‘ [J 81
`
`=xp(—j2mrxr)+ q 32
`
`exp(—j27tuxz)+ . . . ] otherwise
`
`where on is a constant that ensures that |F(u)| is normalized
`This complex-valued filter function, F, will be implemented
`on the available spatial light modulator using the methods
`described in the article “Optimal realizable filters and the
`minimum Euclidean distance principle,” Richard D. Juday,
`Applied Optics, Vol. 32 pages 5100—5111 (1993), or by other
`such methods.
`
`One knowledgeable in the art can easily extend this to two
`dimensions. The unique filter generator outputs the values of
`the filter F to card storage device 22 on line 46. The card
`storage device stores filter F on a storage medium (such as
`a magnetic strip or smart card chip) of a card 20. Once this
`operation is accomplished, enrolment is complete and the
`individual leaves with card 20.
`
`A subscriber may communicate his public key or decrypt
`a message utilizing apparatus 70 of FIG. 2. Further, another
`may encrypt a message with apparatus 70.
`Turning to FIG. 2, apparatus 70 comprises an input
`system 129 with a laser 130, expander lens 131, collimator
`lens 133, and prism 135 which may be similar to the input
`system 29 of FIG. 1. A correlator 142 is in the information
`beam path 139. The correlator comprises a Fourier trans-
`forming lends 143, an electronically addressable
`(programmable) spatial light modulator (SLM) 144 in the
`back focal plane of lens 143, and an inverse Fourier trans-
`form lens 146. The output beam 147 from the correlator
`inputs optical detector 148. Detector 148 inputs processor 80
`on line 149. The processor also receives an input from card
`reader 72 on line 78. The processor outputs to the SLM 144
`on line 79, to a pseudo-random number generator 84, and to
`a public/private key generator 88 on line 82. The pseudo-
`random number generator outputs to the public/private key
`generator which, in turn, outputs to a public key communi-
`cator 94 and, on line 92, to a decryption/encryption system
`96. The public/private key generator also receives an input
`from public key receiver 95 and from keypad 74. The
`decryption/encryption system receives an input from an
`input message store 98 and outputs to an output message
`store 100.
`
`A subscriber who wishes to transmit his public key places
`the same finger or fingers on the input screen 128 as were
`placed on the screen 28 (FIG. 1) during enrolment, his card
`20 in reader 72, and presses button 76 of keypad 74. This
`activates light source 130 and the resulting output beam 139
`from the prism is an information beam carrying the finger-
`print pattern p'. The beam 139 carrying the spatial fingerprint
`information proceeds into the correlator 142 and passes
`through the Fourier transform lens 143. The filter
`information, F, stored on card 20 is read by reader 72 and
`input to processor 80. The processor converts the incoming
`digital filter infomation signals to analog SLM drive volt-
`ages. These drive voltages, which represent the filter
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`degree of correlation between the input fingerprint(s) p' and
`the reference fingerprint(s) p used to construct the filten' F. If
`p and p' are the same fingerprint(s) the 5' equals S. The
`optical signal 145 which comprises 8' passes through the
`second transform lens 146 and onto the optical detector 148
`where its intensity distribution 5' is detected. When p‘ equals
`p then s' will be an intensity distribution representing g, the
`array of numbers which represent the unique number n. The
`output of the optical detector 148 inputs the processor 80
`which calculates the unique numbers u from the array of
`numbers {g1, .
`.
`. g}. If the error in detection by detector
`148 only allows [3 distinct values between 0 and m—l
`inclusive, where m is the dynamic range of the optical
`detector 148, we calculate:
`
`gifigimeasured)~% and round to integers
`where Oégikfi.
`Then 13:81*Bh_1+82*fln_2+. . . +5330
`
`The number n then ads as the seed number which inputs
`pseudo—random number generator 84. It is important to note
`that the pseudo-random number generator will generate the
`same random numbers whenever it is input with the same
`seed,
`in this case 11. The random numbers derived by
`pseudo-random number generator 84 as well as 11 itself, on
`line 82,
`input
`the key generator 88. The key generator
`utilizes known public-key cryptographic techniques to
`derive a private key or a public key fi‘om these inputs. With
`button 76 of keypad 74 depressed, the key generator is
`prompted to output the public key on line 90 to public key
`communicator 94. Communicator 94 may simply be a
`display or it could be a transmitter such as a modem which
`transmits the number to a sendec.
`If a subscriber has an encrypted message he wants to
`decipher, he may utilize apparatus 70 to decrypt same, as
`follows. The encrypted message is input to input message
`store 98. Then the subscriber (receiver) inserts his card 20 in
`card reader 72, depresses button 79 of keypad 74, and places
`his finger(s) on input screen 128. As before, the processor 80
`generates the unique number n from the intensity distribu—
`tion s‘ and this, along with the random numbers generated by
`random number generator 84 in response to the seed number
`11, input the key generator 88. In response to the prompt from
`button 79, the key generator utilizes these inputs to derive
`the private key. The private key then inputs decryption/
`encryption system 96 on line 92; the encrypted message
`stored in the input message store 98 also inputs system 96.
`The system 96 utilizes known public key cryptographic
`techniques to decrypt the message from these inputs. The
`decrypted message is then output to output message store
`100 where it may be accessed by the subscriber.
`
`

`

`5 ,680,460
`
`7
`If the person using apparatus 70 was not the person whose
`fingerprints were represented by the encoded filter F. then
`the optical signal S‘ derived from the multiplication of the
`filter F from the card with the Fourier transform P‘ of that
`persons fingerprint(s) will not equal S. This will mean that
`the unique number u' indirectly derived from S‘ will not be
`equivalent to u. Consequently the key generated by the
`private/public key generator 88 will not decrypt
`the
`encrypted message.
`An individual may send a subscriber an encrypted mes-
`sage utilizing apparatus 70 in the following manner. The
`individual stores a plain text message in input message store
`98, depresses button 77 of 'operator input 74 and inputs the
`public key of the subscriber to public key receiver 95. This
`prompts the key generator 88 to directly input the public key
`from public key receiver 95 to the decryption/encryption
`system 96. The system 96 uses this key in encrypting the
`plain text message and outputs the encrypted message to
`output message store 100. The individual may then transmit
`the encrypted message to the subscriber in any non—secure
`manner. (It may be noted that the fingerprint and card
`reading subsystems of apparatus 70 are inactive when button
`77 is pressed.)
`It will be apparent that the system of this invention allows
`the use of public key encryption techniques without a
`subscriber knowing his private key. This enhances the
`security of the system. Yet further a lost card could not be
`used by a third party in apparatus 70 because the unique
`number 11 is only recoverable by inputting the subscriber’s
`fingerprint.
`Another advantage of the subject system is that the
`subscriber need not know his public key as it may be easily
`generated with the system of the invention. Furthermore, if
`an unauthorized individual broke in to an apparatus 70 of
`FIG. 2, he would have no way of determining the manner for
`generation of u since this number is only generated in the
`enrolment devices of FIG. 1 and is unique to each individual.
`The robustness of the system of the present invention may
`be enhanced as follows. In the enrolment apparatus 10 of
`FIG. 1, the absolute value. of one point of g={g1, . .
`. gn}, for
`example g1, may be stored on card 20. If this is done, then
`the processor circuit 80 of FIG. 2 may compare the intensity
`of this same point in the g function generated by optical
`correlator 142 with that point stored on the card and scale the
`elements of g from correlator 142 accordingly. This will
`reduce the effect of the “noise” present in apparatus 70. For
`example, dirt or oil on the input screen 128 could reduce the
`absolute intensity of g. However, the relative intensities of
`the delta functions would be preserved. The absolute value
`could then be recovered by comparing one point of g
`generated by correlator 142 with that same point of g which
`is stored in absolute form on card 20.
`the unique
`In another embodiment of the invention,
`number, 11, is related to the location of peaks in the correlator
`output, rather than their relative intensities as considered so
`far. In this embodiment the filter F is designed to produce a
`series of equal-intensity peaks at the correlation plane detec-
`tor. The peak locations are carefully controlled so that the
`occur within a grid of p by q cells on the detector. When n
`such series of peaks are displayed sequentially, the unique
`number u can be reproduced, using only the peak location
`information.
`In this embodiment an individual will be enroled using the
`following procedure. With reference to FIG. 1, the indi-
`vidual will place their finger(s) on the input screen 28. As
`before, the fingerprint information is input to eh ICDD 41.
`The digital output 42 of the ICDD is input to the unique filter
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`65
`
`8
`generator 43 and to the unique number generator 44. The
`unique number generator 44 will assign the subscriber a
`unique number u as previously described. Then, the unique
`number generator 44 determines an array b which is related
`to the unique number u by the following relationship:
`
`u=f<b.w)
`
`where w is a constant for any specified number of peaks (t)
`and size of grid (p by q) as described hereinafter. For reasons
`which will also be apparent hereinafter, a convenient choice
`for the function is:
`
`u=blw""+b2w"'2+. . . +b,,_1w‘+b,,w°
`
`. bu which determine the
`.
`Thus, the coefficients b1, b2.
`unique number u can be evaluated using modular arithmetic
`as follows:
` _ H
`
`b; _ Integer of W1
`
`1
`b, = my, date-MLwn—Z
`2
`bf, = mg... offlw].
`l.
`
`b,I = Integer of mod wwe
`
`The unique number generator 44 then assigns each value
`of b1 to one of the possible permutations of arrangingt peaks
`in a grid of p by q cells. One of the peaks is always located
`in the upper left cell of the grid, to serve as a reference peak.
`The number of permutations of locating the remaining t—l
`peaks in the p-q—l cells is given w, where:
`
`- —1!
`_
`W‘ (r—mo-q—t)!
`
`Thus, it is clear that each coefficient b1 has a value
`between 0 and w—l inclusive. The assignment of the value
`of b1 to a particular pattern of peak locations is accom—
`plished by using a randomised look-up table in the filter
`generator which relates every possible value of b1(i.e. from
`0 to w—l) to a unique permutation of peak locations in the
`grid. Thus, a two-way relationship between the value of b1
`and the relative locations of peaks in the grid is established.
`Clearly then, if the subscriber can later reproduce the pattern
`of peaks in such a grid using the apparatus 70 of FIG. 2, then
`the unique number 11 can be regenerated and thus the
`subscriber can proceed. Note however, that because of the
`randomised look-up table, even if a pattern of peaks were
`discerned, it would bear no relationship to the corresponding
`value of the element of b unless the look-up were known.
`The required locations of the peaks for each element, bi,
`of b are input to the unique filter generator from the unique
`number generator. The unique filter generator calculates the
`filter, Fi,
`so that when the correct fingerprint (or
`fingerprints), p, is input to apparatus 70 of FIG. 2, the output
`functions, si, is the specified arrangement of equal-intensity
`peaks. This calculation uses the Fourier transform of the
`subscriber’s fingerprint(s), P, and the same approach as
`described previously, with the exception that all of the
`delta-like functions are assigned the same peak height, and
`their relative locations are determined by b,. (Therefore, in
`one dimension,
`
`

`

`5,680,460
`
`s,=8(x—x1)+8(x—x2)+. .
`
`9
`. +5(x—x,)
`
`, x, are determined by the look-up table of
`.
`.
`where )9, x2, .
`peak locations for bi.) Note that n such filters, F1, F2, . . . F",
`corresponding to b1, b2, . .
`. b", will be required to determine
`all the elements of b. The n filters are generated in this
`manner, and are then stored on the card 20. Thus, the
`enrolment process is completed and the user retains the card
`20.
`
`Where the subscriber to the system wishes to regenerate
`the unique number, u, to produce the private or public key,
`the following procedure is adopted. Thrning to FIG. 2, when
`a subscriber places his finger(s) on the input 128 of appa-
`ratus .70, inserts his card 20 in the reader 72, and presses
`button76 (to display his public key) or 79 (to decrypt a
`message), the processor causes the n filters from the card 20
`to be transferred sequentially to the SLM 144 on line 79. A
`given filter, F1, is multiplied in the correlator 142 with the
`Fourier transform, P, of the subscriber’s fingerprint(s). The
`inverse Fourier transform of the result, which is the function
`s,-, is displayed on the correlation plane detector 148. With
`reference to FIG. 3, which schematically illustrates a portion
`of FIG. 2. the location of the first peak 150 in the detector
`148 is determined by scanning across the detector from
`upper left to the bottom right. This first peak is considered
`to be the reference peak, and its position defines the grid 15]
`of p by q detection cells in the correlation plane detector,
`with the reference peak occupying the upper left cell in this
`grid. The detector output is then scanned over the are of the
`grid 151 and the locations of the other t—l peaks are
`determined. Each of the t—1 peaks occupies a unique cell in
`the grid and the position of each is communicated to the
`processor 80 on line 149. The processor determines the
`element b,- of the vector b from the pattern of peaks by
`referring to the same randomised look-up table as used in the
`unique filter generator 43. The next filter, Pi, is then written
`to the SIM and thus the next element of b is determined and
`son on, until the entire array, b, is generated.
`Since each element b,, will have w possible values, b,, is,
`in eifect, a number in base w. It is for this reason that
`
`Ll=f(b,W)
`
`is chosen as
`
`u=b,v'-1+b2w"-2+. . . +b,,_,w1+b,,w°,
`
`because this equation converts the n elements of b from base
`w to base 10 which is more suitable for communication
`purposes. Thus. the unique number n is recreated using the
`apparatus 70 of FIG. 2, and can be input to the pseudo-
`random number generator.
`In the example shown in FIG. 3, t=4 (there are 4 peaks),
`p=q=4 (a 4X4 detection gridis defined), and n=4 (4 filters are
`displayed sequentially). Thus, in this example, the unique
`number u would be capable of representing 4554 or 4.3><1010
`values.
`.
`Thi