Abstract:
A system providing access control, including encryption and decryption capability, replaces a public key directory by a transmission between an authority, or a sender S, and a receiver R of a &#34;seed&#34; value. The seed is processed to provide both identity information for R and public keys, i.e. a &#34;virtual public key directory&#34;, or VPKD. The VPKD is generated prior to execution of the algorithm requiring the public directory, i.e. the host algorithm.

Description:
This is a continuation of application Ser. No. 08/094,931, filed Jul. 16, 1993, now abandoned. 
    
    
     The present aplication is a continuation of International Patent Application Number PCT/EP92/00044 filed 11 Jan. 1992 by David Naccache and having the same title as the present application. 
     FIELD OF THE INVENTION 
     The present invention relates to a method and to an apparatus for access control and/or identification which requires no public key directory. 
     BACKGROUND 
     For many applications, e.g. smart cards for pay TV purposes, credit cards, passports, dongels, military command and control systems, unforgeable systems for access control or digital signature are required. Such access control and signature systems may include public keys. But in many public key identification and access control systems the key management becomes very complicated when the number of users increases. Typical problems are: 1) the memory size of the public directory; 2) interaction with the directory is needed whenever users want to communicate causing simultaneous access problems if the directory is not duplicated; 3) the &#34;blacklisting&#34; of invalid and old keys; 4) adding a new member (e.g. &#34;allusers&#34; update mail to the members); 5) risks of forgery of the public directory (e.g. interchange of public keys between an authorized user and an unauthorized party attempting to gain access). Entities might try to duplicate, playback, or forge key identification devices (hereafter called `identifiers` because they identify authorized users). 
     A known solution to this problem of digital identification and signature is described in European Patent Applications EP 0252499 and EP 0325238 by Fiat and Shamir. This method utilizes a trusted authority which issues an identifier to each authorized user. No further interaction with any center is required. In particular, no interaction is required for either generating or verifying identities and signatures. An unlimited number of users can join the system without statistically compromising its security. Interactions with identifiers do not allow forgery of identifiers. No user or verifier directories are needed. 
     Although the known approach disclosed in, for example, EP 0252499 works well in many applications, certain theoretical aspects may result in compromised security. A brief summary of the protocol, i.e. the flow scheme, which is disclosed in EP 0252499 follows. In the following description, 
     U is an user, e.g. a smart card; 
     V is a verifier; 
     k is an integer number, e.g. in the range [1,18]; 
     r is a random integer number in the range [0,n); 
     (e 1  e 2  e 3 . . . e k ) is a binary vector. 
     In the known approach, an &#34;authority&#34; chooses a pseudo random function f and a modulus n=pq, where p and q are both prime numbers that are known only to the authority (A=B mod n is equivalent to mod (A,n)=mod (B,n)). To issue an identifier, the authority: 
     1) prepares a string ID containing information which is unique to the entity U; 
     2) computes a set of values v ji  =f(ID,j i ) for small values of j i  ; 
     3) selects k values of the v ji  which are quadratic residues mod n and computes the values s ji  such that s ji   2  *v ji  =1 mod n; 
     4) issues an identifier containing ID, j 1 ,i 2 , . . . , j k ,s j1 ,s j2 , . . . , s jk  and n. 
     The identity verification protocol between user U and verifier V then proceeds as follows: 
     1) U sends ID and j 1 ,j 2 , . . . , i k  to V; 
     2) V generates the v ji  by computing v ji  =f(ID,j i ) for i=1,2, . . . , k; 
     3) U picks a random r and sends r 2  mod n to V; 
     4) V chooses a binary vector (e 1  e 2  e 3 . . . e k ) and sends it to U; 
     5) U multiplies r by each of the s ji  values where bit ##EQU1## (for example, if the binary vector is 1100100000, then y=r*s j1  *s j2  *s j5  mod n); 
     V checks that ##EQU2## 
     The security of the described protocol can be compromised in a number of ways. Three techniques, designated A, B, and C, are described below. 
     A) If an unauthorized user U attempts to gain access and discovers only one of the s ji , e.g. s jc , the system becomes vulnerable to the following scheme in which user U successfully misrepresents himself: 
     U sends ID and j c ,j c , . . . , j c  to V; 
     V generates k times the sane v jc  since all the j i  are identical; 
     U picks a random r and sends r 2  mod n to V; 
     V chooses a binary vector (e 1  e 2  e 3 . . . e k ) and sends it to U; 
     U sends to V ##EQU3## V checks that ##EQU4## B) This approach is less difficult than &#34;A&#34; above because it is easier mathematically to compute the inverse of one of the v ji , e.g. v jc   -1 , than it is to compute the inverse root s jc . If such a value is known then the probability is 0.5 that the above-described known identification system can be compromised as follows: 
     U sends ID and j c ,j c , . . . , j c  to V; 
     V generates k times the same v jc  since all the j i  are identical; 
     U picks a random r and sends r 2  mod n to V; 
     V chooses a binary vector (e 1  e 2  e 3 . . . e k ) and sends it to U; 
     U sends to V y=r(v jc   -1 ) int  (Σe i  /2) mod n; 
     V checks that ##EQU5## 
     This test will be true if Σe i  is even. 
     If a pay TV verifier is public and available in any desired quantity, an entity attempting to gain unauthorized access could use four verifiers simultaneously to obtain, for example, a TV program descrambled up to 94% by using approach B. If four additional verifiers are added, the percentage of descrambled TV content is increased to 99.6% which provides acceptable image quality. 
     C) The third approach, referred to as &#34;signature forgery&#34;, is the most dangerous approach because it permits any verifier to forge signatures from only public data. Signature forgery proceeds as follows: 
     U sends ID and j c ,j c , . . . , j c  to V; 
     V generates k times the same v jc  since all the j i  are identical; 
     U executes the following algorithm: ##EQU6## The probability that such an r will not be discovered decreases exponentially following the law of 2 - χ. Typically, the probability that a desired r will be found before x=7, where x is the number of iterations of the WHILE loop, is about 99%. 
     U sends y together with (e 1  e 2 . . . e k ) to V; 
     V successfully compares ##EQU7## The weakness of the known system resides in the fact that the v j  (j=1,k) values are considered to be k different secret values and, therefore, forging a part of them (here 1/18, k=18), e.g. using the described signature forgery approach, compromises the security of the scheme. 
     SUMMARY OF THE INVENTION 
     It is an object of the invention to provide a method and apparatus for improving the security of an access control system. A second object of the invention is to allow the introduction of data from previous communications between user and verifier to the next ones, thereby further improving security. Another object of the invention is to provide a method for identification which enables any user to prove his identity. 
     The invention uses the fact that it is difficult to compute square roots mod n when factoring of n is unknown. The invention is based on the identity: 
     
         x.sup.2 {r(x+x.sup.-1)}.sup.2 =r.sup.2 {1+x.sup.2 }.sup.2 mod n(1) 
    
     which is computed and compared using a user unit and a verifier unit. Equation (1) is difficult to solve and to imitate by an unauthorized user from only public and transmitted data. Advantageously, equation (1) can be generalized to: 
     
         x.sup.ε {r(ax+bx.sup.-1)}.sup.ε =r.sup.e {b+ax.sup.2 }.sup.ε  mod n                                    (2) 
    
     in order to increase protection and to introduce more noise into the communicated data as explained below. 
     The invention provides a method and apparatus for solving the above-described problems. The algorithm which requires a public directory (hereafter referred to as &#34;host algorithm&#34; or &#34;host protocol&#34;) uses a modulus n which is the product of at least two large prime numbers. The known public key directory is replaced by a unique transmission of a &#34;seed&#34; value between an &#34;authority&#34;, or a sender, S and a receiver R. Proper processing of the seed will provide both the identity information for R and public keys. This method is referred to as &#34;Virtual Public Key Directory&#34; or VPKD. 
     Advantageously, VPKD can be standardized and introduced to any security protocol requiring public moduli. New users can join the system without informing other users and verifiers, and without compromising the security of the system or reducing its performance. Only an authority that will provide seeds must know the factoring of n. 
     Typically, a VPKD will precede the host protocol. In practice this can be viewed as a preliminary secure communication that will give S public data signed by the authority. This is illustrated in FIG. 7. The evolution of knowledge between R and S is depicted in FIG. 8 for an identification system and in FIG. 5 for an access control system. 
     FIG. 6 explains the construction of a VPKD pre-protocol device. In order to register a new user U, the authority computes a public key PK U  such that PK U  &lt;n (this restriction can be removed if PK U  is sliced to the right size as is commonly done in modulo-based crypto systems) and prepares a string ID U  which is unique to the physical entity U or to a given group of members and contains information such as name, address, credit card number and date of validity. This can be done by a first unit 61. A second unit 62, e.g. a memory, contains the value n. Then the center concatenates within a third unit 63 ID U  and PK U  with a well chosen byte c such that ID U  &amp;PK U  &amp;c has a d-th root modulo n (the symbol &#34;&amp;&#34; indicates concatenation). 
     This root is designated g U  where g U  is defined by G U  =g U  mod n where G U  =ID U  &amp;PK U  &amp;c. At manufacturing g U , ID and n are recorded on a retrieval medium 64. When S interacts with U, S sends g U  to U which computes G U  by raising g U  to the power d. Next, ID U  and PK U  are separated and used by the host protocol. In a typical implementation, a value d=2 or d=3 may be chosen. 
     The described method can be generalized in various ways such as the following. 
     1) The order of ID, PK, and c in G can be permuted. A normalization will appear to be good in practice since the VPKD can be used by all different modulo based algorithms requiring public key transmissions. 
     2) Public or secret reversible functions for mixing and separating ID, PK and c can be used instead of simple concatenation, e.g. compression, permutation or even recurrent nested VPKD. 
     3) In schemes requiring k different public key values PK U1 ,PK U2 ,PK U3 , . . . , PK UK  (for each user U), which can be permuted without compromising the functionality of the scheme (concerning the known identification system where all the v j  play the same role provided that for each s j   2  v j  =1 mod n), the use of c can be avoided by permuting: ##EQU8## until a G U ,.sub.μ  which is a d-th power mod n is found. The probability that an appropriate G U , .sub.μ will not be found is 
     
         (3/4).sup.18! &lt;1O(.sup.-ex),ex=10.sup.14 
    
     4) Checksums, random &#34;one way&#34; functions, CRCs (cyclic redundancy check) and other mathematical methods can be included in G (e.g. f(ID,PK) where f maps long strings to a few bytes). In systems where a group (or all entities) has the same ID (or no ID at all), ID can be eliminated or replaced by a constant. This may be applicable to pay TV systems in which it is often desirable to address groups of subscribers. 
     5) ID and/or the PK can be transmitted in a plain or enciphered form along with the corresponding g to improve security. 
     6) Simple exponentiation of g can be replaced by a polynomial computation. To provide this capability, the authority publishes a sequence of numbers Ω i  and computes g U  in such a way that ##EQU9## 
     Simplicity, security and speed aspects of the invention are enhanced through the use of microprocessor-based techniques. For example, microprocessor based apparatus embodying the invention may be incorporated into smart cards, personal computers, dongles, passports and other remote systems. These systems are useful in various applications including pay TV. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     The invention may be better understood by referring to the accompanying drawing, in which: 
     FIG. 1 shows a pay TV system with scrambling and encrypting units; 
     FIG. 2 shows the hardware and software structure of an identifier U (smart-card); 
     FIG. 3 shows the hardware and software structure of a verifier V; 
     FIG. 4 shows an authentication protocol between a signer (smart card) and a verifier (identity control device) containing no secure information; 
     FIG. 5 illustrates a typical chronological evolution of information retained by R and S in a communication involving a VPKD pre-protocol and an access control algorithm; 
     FIG. 6 shows the construction process of a VPKD pre-protocol apparatus; 
     FIG. 7 shows a VPKD pre-protocol and a host protocol; 
     FIG. 8 illustrates a typical chronological evolution of information retained by R and S in a communication involving a VPKD pre-protocol and an identification algorithm. 
    
    
     DETAILED DESCRIPTION 
     Satellite broadcasters are now using conditional access systems to ensure that TV programs are available only to authorized viewers, i.e. viewers who have fulfilled certain conditions such as paying required access fees. A pay TV system may be considered to include two parts. The first part is a scrambling system for processing the video signal such that the received picture is not &#34;viewable&#34; by unauthorized viewers. An example of a scrambling approach is a line cut and rotate method that is described in more detail below. A second part of a pay TV system is an encryption system for processing key signals needed to descramble a scrambled video signal. 
     FIG. 1 shows a known pay TV system, e.g. the Videocrypt system. The incoming studio video signal 10 is scrambled in a video scrambler 122 which is controlled by a data insertion unit 121. The data insertion unit receives access control data from an encryption computer 11 and inserts data in the vertical blanking interval of the video signal which is processed by an authorized decoder to descramble the video signal. The RF modulated output signal 13 of the emitter side is the input signal 14 at the receiver side. This input signal becomes demodulated in a tuner 15 and is fed to a data extraction unit 16 and to a video descrambler 17. The access control data out of data extraction circuit 16 are evaluated in a verifier unit 181 if a smart card 182 is inserted. The output signal of the verifier unit controls the video descrambler 17. 
     The lines of the video signal which shall be scrambled consist of a first segment and a second segment. These two segments are separated by a cut point cp. There are, for example, 256 different cut points available within each line. A complete line may consist of 958 samples of the digitized luminance and chrominance signal, respectively. 
     The cut point is defined at each line by a pseudo-random binary sequence (PRBS). The two line segments then become rotated within the line, i.e. they change their position within the line. The location of cut point cp varies within the lines of each TV picture. It is the task of the descrambling system in the receiver to restore the original positions of the two segments. The encrypted data necessary to restore the segment positions may be inserted in the vertical blanking interval. 
     To descramble the TV signal, the decoder includes the same PRBS generator (verifier unit 181) as in the emitter (encrypting computer 11). Both generators are initialized with the same control binary sequence, e.g. a control word. The control word is changed every few seconds and transmitted in encrypted form simultaneously to all decoders. 
     The PRBS generator may output two 8 bit words. These words can mark the cut points cp in a luminance and in a chrominance line, respectively, as follows: 
     
         ______________________________________Byte      Cut Point is at sample______________________________________0         224cp        224 + 2 cp255       734______________________________________ 
    
     Before issuing identifiers, the authority chooses and makes public a modulus n and a power ε (typically ε=2) to all those who might have to check identities or signatures. The center (i.e. the authority) then produces VPKD devices for all authorized members. The VPKD devices contain k small (typically between 1 and 5 bytes) public key values PK j  so that each PK j  has ε-roots mod n (hereafter denoted SK j   -1 ) whereby PK j  is not a perfect square in N. If possible, prime PK j  values must be chosen. In implementations where ε is not equal to 2, means for communicating SK j   -2  to V must be found as well (VPKD, public directory, etc.). When this is done, the authority records on a retrievable medium the identifier U containing g, n, ε and the respective SK j  values. 
     For a typical implementation the following values are suggested: 
     twenty values PK of 2 bytes each; 
     a 128-bit ID and a 8-byte checksum on ID&amp;PK 1  &amp;PK 2  &amp; . . . &amp;PK 20  ; 
     |n|=512 bits. 
     Optionally, one can add into the identifier any algebraic or electronic functions &#34;a&#34; and &#34;b&#34; as indicated in equation (2) above. If this is done, however, a and b must also be known to the verifiers. Advantageously, in typical small implementations (e.g. smart-cards) both a and b are constants with a value 1, but in a more powerful system (e.g. dongle) a and b can be any functions. 
     A typical access control implementation is depicted in FIGS. 2 and 3. A smart-card 20 (i.e. the identifier U) is connected with its I/O (input/output) interface 21 to the I/O interface 31 of a verifier unit 30. Smart-card 20 contains, for example, a microprocessor 24 and a memory 25 such as a ROM (read-only memory). The memory may contain the values g, n, SK j  and a program for controlling microprocessor 24. The verifier unit 30 may also contain a microprocessor 34 and a memory 35, e.g. a ROM. The verifier memory may contain the value n and a program for controlling microprocessor 34. 
     When the identifier interacts with the verifier, the following actions occur. 
     1) The identifier U sends g to V (and SK 1   -2 ,SK 2   -2 , . . . , SK k   -2  if ε not equal to 2 and if this data is not transmitted or known to V by another way). 
     2) V computes g 2  mod n and finds G=ID&amp;PK 1  &amp;PK 2  &amp; . . . &amp;PK k . Then V separates ID and the PK values found in g 2  mod n. 
     3) U picks a random δ in the range [√n+1,n/2), computes E=δ.sup.ε  mod n and sends E to V. 
     4) V selects a random binary vector v=(v 1  v 2 . . . v k ) and sends it to U. 
     5) Optional--only if functions a and b are used: both V and U prepare an identical value Ω (e.g. from v, δ, previously transmitted information, etc.). 
     6) U computes ##EQU10## and sends z to V. 7) V checks that ##EQU11## 8) Repeating steps (3) through (7) at least once. 
     The described protocol can be modified in various ways. For example, a variety of polynomial identities can be used instead of equation (1) above. 
     FIG. 4 shows the corresponding authentication protocol. 
     Advantages provided by the invention include the following. 
     1) No pseudo random functions are needed. This requires less memory capacity (in ROM) and reduced program complexity. 
     2) All the public key values are computed by a unique computation that provides a substantial reduction in computation time. In comparison, known identification schemes require that k independent operations, namely f(ID,j), must be carried out. 
     3) The known pseudo random function f gives v j  of unforseeable sizes whereas the invention provides for selecting any (PK j , SK j ) pair and, in particular, pairs where both, SK j  and PK j , are of small size. 
     4) When the known identification system is upgraded (changes in function f), all old identifiers become obsolete. This problem does not exist with systems constructed in accordance with the invention because no function f is used. 
     The authentication protocol, or digital signature protocol, of Fiat-Shamir that is discussed above can also be improved if additional security tests performed by the verifier are carried out after the reception of the indices j i  from the prover. These security tests are that for all 
     
         l≦a&lt;b≦k, j.sub.a not equal j.sub.b, 
    
     and/or 
     
         l≦a&lt;b≦k, v.sub.a not equal v.sub.b.