Aperiodic encryption for digital data6792108Abstract For stream or block ciphers, a sequence generator using a quasi-crystal function is used to prepare an encryption or decryption pad. Various techniques for generating purely aperiodic sequences using quasi-crystal functions are available, including geometric, algebraic and symbolic substitution. The aperiodic sequence is generated using minimal processing power, and generation may continue for extended periods of time in the case of long messages or extended period encryption of a data transmission channel. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 1
c.sub.1 c.sub.2
i a.sub.i b.sub.i a.sub.i + b.sub.i.tau. a.sub.i + b.sub.i.tau..sup.2
c.sub.1 (binary) c.sub.2 (binary)
0 0 0 0.0000 0.0000 0 0000 0 0000
1 1 1 2.6180 0.3820 7 0111 11 1011
2 2 2 5.2361 0.7639 14 1110 6 0110
3 2 3 6.8541 0.1459 14 1110 1 0001
4 3 4 9.4721 0.5279 5 0101 12 1100
5 4 5 12.0902 0.9098 12 1100 7 0111
6 4 6 13.7082 0.2918 12 1100 2 0010
7 5 7 16.3262 0.6738 3 0011 13 1101
8 5 8 17.9443 0.0557 3 0011 8 1000
9 6 9 20.5623 0.4377 10 1010 3 0011
10 7 10 23.1803 *0.8197 1 0001 14 1110
11 7 11 24.7984 0.2016 1 0001 9 1001
12 8 12 27.4164 0.5836 8 1000 4 0100
13 9 13 30.0344 0.9656 15 1111 15 1111
14 9 14 31.6525 0.3475 15 1111 10 1010
15 10 15 34.2705 0.7295 6 0110 5 0101
16 10 16 35.8885 0.1115 6 0110 0 0000
17 11 17 38.5066 0.4934 13 1101 11 1011
18 12 18 41.1246 *0.8754 4 0100 6 0110
19 12 19 42.7426 0.2574 4 0100 1 0001
The table shows an example of 20 points of the 2-tile quasi-crystal with acceptance window (W.sub.2, W.sub.1)=(0,1). Each line refers to one quasi-crystal point, the first one being the seed point. In column 1 the lines are numbered. Columns 2 and 3 contain respectively the components a.sub.i and b.sub.i of the quasi-crystal point Y.sub.i =a.sub.i +b.sub.i.tau., 0 .ltorsim.i .ltorsim.19, Column 4 contains Y.sub.i as a rounded real number. In column 5 we show the image Y.sub.i '=A.sub.i +b.sub.i.tau.' of Y.sub.i in the acceptance window; asterisks identify the values of Y.sub.i ' in the window (V.sub.2,V.sub.1)=(0.8,0.9) of the subquasi-crystal which determines the position of random bits. Colomns 6 and 8 contain the colors c.sub.1 and c.sub.2 of Y.sub.i as integers modulo 16 respectively. Column 7 and 9 contains the same colors c.sub.1 and c.sub.2 written in binary form. The first example has the `simplest` possible values in its key: all parameters equal 0 except for c, the length of the acceptance window, which has to be positive and is set to 1. Since c=1, it is a 2-tile quasi-crystal. The first 20 points a.sub.i +b.sub.i.tau. (0.ltorsim.i.ltorsim.19) are shown in Table 1. Each of the 20 lines refers to one quasi-crystal point, the first one being the seed point. In the first column, the points are enumerated. In the next two columns, the integer components a.sub.i, b.sub.i of each point are shown; and in column four the point is given as a rounded real number. Column five contains the rounded real number a.sub.i +b.sub.i.tau.'. It gives the position of the image of the point in the acceptance window. Reading the first few points from that table, the values are 0,1+.tau.,2+2.tau.,2+3.tau.,3+4.tau.,4+5.tau.,4+6.tau.,5+7.tau. Note that the distance between any pair of adjacent points is either .tau.+1=.tau..sup.2 or .tau. as one should expect in a 2-tile quasi-crystal. EXAMPLE 2 There are 20 points in the second example. They are shown in Table 2. They were generated for a three tile quasi-crystal with an acceptance window length of 1,4984 with W.sub.1 =1.1988. The four decimal places of precision for the acceptance window values is chosen arbitrarily for both the transmission and receiving ends, and the amount of precision should be different (greater of even less). In this example, the seed point is not the origin but rather a.sub.0 +b.sub.0.tau.=4483+7251.tau., The image of the seed point in the acceptance region is a.sub.0 +b.sub.0.tau.'=4483+7251.tau.'.apprxeq.1.6355. The first few points are the following: 4483+7252.tau., 4484+7251.tau., 4484+7252.tau., 4484+7253.tau., 4485+7253.tau., 4485+7254.tau., 4486+7255.tau., 4486+7256.tau., . . . Here the distances between adjacent points are either 1, .tau., or .tau.+1 as one should expect in a 3-tile quasi-crystal.
TABLE 2
c.sub.1 c.sub.2
i a.sub.i b.sub.i a.sub.i + b.sub.i.tau. a.sub.i + b.sub.i.tau.'
c.sub.1 (binary) c.sub.2 (binary)
0 4483 7251 16215.3645 1.6355 1 0001 12 1100
1 4484 7257 16216.3645 2.6355 3 1011 11 1011
2 4484 7252 16217.9825 2.0175 12 0000 0 0000
3 4484 7253 16219.6005 1.3995 5 0101 5 0101
4 4485 7253 16220.6005 2.3995 7 0111 4 0100
5 4485 7254 16222.2186 1.7814 0 0000 9 1001
6 4486 7255 16224.8366 *2.1634 11 1011 13 1101
7 4486 7256 16226.4546 1.5454 4 0100 2 0010
8 4487 7256 16227.4546 2.5454 6 0110 1 0001
9 4487 7257 16229.0727 1.9273 15 1111 6 0110
10 4487 7258 16230.6907 1.3093 8 1000 11 1011
11 4488 7258 16231.6907 2.3093 10 1010 10 1010
12 4488 7259 16233.3087 1.6913 3 0011 15 1111
13 4489 7259 16234.3087 2.6913 5 0101 14 1110
14 4489 7260 16235.9268 2.0732 14 1110 3 0011
15 4489 7261 16237.5448 1.4552 7 0111 8 1000
16 4490 7261 16238.5448 2.4552 9 1001 7 0111
17 4490 7262 16240.1628 1.8372 2 0010 12 1100
18 4490 7263 16241.7809 1.2191 11 1011 1 0001
19 4491 7263 16242.7809 *2.2191 13 1101 0 0000
The table shows an example of 20 points of the 3-tile quasi-crystal with acceptance window (W.sub.2,W.sub.1)=(1.1988, 2.6972). Each line refers to one quasi-crystal point, the first one being the seed point. In column 1 the lines are numbered. Columns 2 and 3 contain respectively the components a.sub.i and b.sub.i of the quasi-crystal point Y.sub.i =a.sub.i +b.sub.i.tau., 0.ltorsim.i .ltorsim.19. Column 4 contains Y.sub.i as a rounded real number. In column 5, the image Y.sub.i =a.sub.i +b.sub.i.tau.' of Y.sub.i in the acceptance window is shown; asterisks identify the values of Y.sub.i in the window (V.sub.2,V.sub.1)=(2.15,2.25) of the subquasi-crystal which determines the position of random bits. Column 6 and 8 contain the colors c.sub.1 and c.sub.2 of Y.sub.i as integers modulo 16 respectively. Column 7 and 9 contain the same colors c.sub.1 and c.sub.2 written in binary form. Coloring of quasi-crystal points, generation of the keystream and 3 examples. Once quasi-crystals and aperiodic sequences have been generated (using for example method I, II, of III), the keystream is constructed by coloring selected points of the aperiodic sequence, i.e. assigning binary strings to points of the sequence, strings which are then concatenated to form the keystream. The coloring prescribes how the assignation is performed. Let K be a finite set of binary strings and S some arbitrary set (for example a quasi-crystal .SIGMA.). Each element of K is called a color, and any mapping M: S.fwdarw.K from S to K is called coloring. In the proposed method, a set .SIGMA..sub..LAMBDA. composed of points from one or several quasi-crystals is generated. The points of this set are then colored. More precisely, a set K of colors is defined (either from the key or fixed by the algorithm) as well as a mapping M: .SIGMA..sub..LAMBDA..fwdarw.K from .SIGMA..sub..LAMBDA. to K (again given from the key of fixed by the algorithm). The keystream is then obtained as the concatenated value of all binary strings in M(.SIGMA..sub..LAMBDA.). There exists infinitely many possible M and K, and thus infinitely many colorings. However some colorings lead to cryptographically unsecure ciphers, therefore they must be selected carefully with respect to the specific security requirements of the stream ciphers' applications. There exist mappings such that monochromatic subsets of .SIGMA..sub..LAMBDA. form subquasi-crystals. For example, if .SIGMA..sub..LAMBDA. is a fragment of a single quasi-crystal, the mappings must satisfy the conditions described in the paper by R. V. Moody, Jiri Patera, Colorings of quasi-crystals, Can. J. Phys. 72 (1994) 442-452. Coloring sets can be obtained in many ways. One simple way consists in using PRNG's with good statistical properties (even though K may have a large number of elements, the periodicity of the PRNG insures that it will be finite). In this case, the mapping M is define such that it uses the a periodicity of .SIGMA. to break any pattern in the PRNG, patterns such as the period. As for K, there are infinitely many possible mappings M, but the mapping, along with the set K, must be chosen such that the cipher will be cryptographically secure. We now give examples of colorings. The first example uses a mapping to the set K={0,1, . . . , q.sub.1 }. The mapping is fixed by two integer parameters p.sub.1, q.sub.1, and two basis vectors e.sub.1, e.sub.2 of the lattice of real numbers Z.sup.2. The parameters p.sub.1, q.sub.1, and the vectors e.sub.i can be part of the key or can be fixed in software or hardware depending on the purpose. The points of the quasi-crystals are considered as pairs (m, n) of the lattice Z.sup.2 rather than of the form m+n.tau.. Using such notation, the point is translated or transformed relative to the new basis (m,n).fwdarw.x.sub.1 e.sub.1 +x.sub.2 e.sub.2 by finding the appropriate integers x.sub.1 and x.sub.2. The color c.sub.1 of the point m+n.tau. is given by the prescription (linear coloring) c.sub.1 =p.sub.1 (x.sub.1 +x.sub.2) modq.sub.1. This mapping is however not very secure since for two adjacent quasi-crystal points e>f, .vertline.x.sub.e,1 +x.sub.e,2 -(x.sub.f,1 +x.sub.f,2).vertline..ltoreq.2. An example of a simple non-linear coloring scheme is the following: c.sub.1 =p.sub.1 (x.sub.1.sup.2 +x.sub.2) modq.sub.1. As a last example of coloring, consider the set K=K.sub.1.orgate.K.sub.2.orgate.K.sub.3, where the K.sub.i values are generated from three (possibly identical) PRNG's having good statistical properties (for randomness). The mapping is defined recursively as follows: let e>f be two adjacent quasi-crystal points: ##EQU7## Selecting the elements of the K.sub.i sets properly leads to a coloring much more secure than the two previous ones. This coloring, which is used in the presently preferred embodiment is now discussed in more detail. The discussion is made for two tile quasi-crystals but is easily generalized to three tile quasi-crystals. Let the following PRNG's: ##EQU8## with i=1,2,a.sub.i mod 4=1, and c.sub.i mod2 =1 (.left brkt-bot.X.right brkt-bot.=largest integers smaller than x). Unless a.sub.i is chosen badly, (3.sub.i) is satisfactorily random (with respect to statistical properties (but is not cryptographically secure, and this for all i=1,2 (see D. E. Knuth, Deciphering a Linear Congruencial Encryption, IEEE transaction on information theory, vol. It-31, no. 1, 1985). Indeed, for any fixed `i` one can deduce the parameters a.sub.i and c.sub.i from a finite sufficiently long sub-sequence. The sets k.sub.i are defined as follows: K.sub.i ={x.sub.ij, j=1, . . . , 2.sup.16 }, where x.sub.ij are given by (3.sub.i) for j.gtoreq.2, and x.sub.i,1 are some integers between 0 and 2.sup.16 -1 (which could be, for example, given by the encryption key or fixed in software or hardware depending on the purpose). The mapping M is then defined as follows: if e and f are two adjacent quasi-crystal points, ##EQU9## The strength of this coloring relies on the fact that the values of either PRNG appear aperiodically, thus adding much complexity to the keystream. This example could even lead to a cryptographically secure stream cipher. EXAMPLES 4 AND 5 The linear and non-linear coloring method described above are illustrated in Tables 1 and 2. For each method, two colorings c.sub.1 and c.sub.2 are computed from different parameter values. The coloring method uses in the presently preferred embodiment deals with 16-bit words and can not be illustrated simply. In the first example shown in Table 1, we illustrate two linear colorings where the chosen parameters are the standard basis of the lattice Z.sup.2, e.sub.1 =(1, 0), e.sub.2 =(0, 1) p=7 in the first coloring and p=11 in the second, and q=16 in both. It will be appreciated that the linear colorings in Table 1 yields somewhat predictable values. For example, the values of c.sub.1 (the first coloring) either hold or are incremented by 7, and the values of c.sub.2 (the second coloring) are decrement by 5 in each iteration. For c.sub.1, the values cannot hold for more than one iteration, and they cannot increment for more than two iterations without holding. Therefore, after a hold for c.sub.1, the event of a single increment of a double increment before the next hold is a purely random one. In the embodiment of Table 1, the 20 quasi-crystal points have 7 such events, and the sequence of bits representing these events would be 1101100, where a `1` represents a double increment following a hold, and a `0` represents a single increment following a hold. Of course, the increments of the value c.sub.1 are related to the quasi-crystal points, i.e. a hold is really a .tau. tile and an increment is really a 1+.tau. tile. It will also be appreciated that the quasi-crystal(s) may be used to directly generate values used in encryption, or the quasi-crystal values may be used to alter encryption pad value generator parameters from time to time. In the second example shown in Table 2, we illustrate two non-linear colorings where the chosen parameters are the basis of the lattice Z.sup.2, e.sub.1 =(1, -3) and e.sub.2 =(-1, 2). The remaining parameters are left unchanged: p=7 in the first coloring and p=11 in the second, and q=16 in both. It will also be appreciated that more complex coloring, such as non-linear coloring, allows for quasi-crystal points to be translated and "expanded" into a plurality of bits for encryption purposes. In some encryption circumstances, it may be acceptable for the encryption key to have exclusion rules for certain transitions from one value to the next, since each value may be used to encrypt a very small portion of a message, such as computer words. The effect of the aperiodicity of the quasi-crystal on the encryption of any significant portion of the message susceptible of an attack may thereon be sufficiently strong. Insertion of random bis Insertion of random bits into an encrypted text disrupts the splitting of the text into regular equally sized blocks. In the preferred embodiment, it is governed by a chosen subquasi-crystal. The parameters V.sub.1, V.sub.2 specifying the subquasi-crystal .SIGMA.(V.sub.1, V.sub.2) satisfy W.sub.1 <V.sub.1 <V.sub.2 <W.sub.2 The quasi-crystal points and .SIGMA.(W.sub.1, W.sub.2) are thus of two types: those which belong to the subquasi-crystal .SIGMA.(V.sub.1, V.sub.2) and those which do not belong to it. Relative density of the points of .SIGMA.(V.sub.1, V.sub.2) to all points of .SIGMA.(W.sub.1, W.sub.2) is equal to the ratio of lengths of the corresponding windows .vertline.V.sub.2 -V.sub.1.vertline./.vertline.W.sub.2 -W.sub.1.vertline.. In practice the parameters V.sub.1 and V.sub.2 can either be given independently as part of the key or be determined automatically as functions of W.sub.1 and W.sub.2. Practical considerations should guide the number of random bits to be inserted and their types. The random bits use additional bandwidth during transmission and are simply ignored when received. Another possibility is to send simultaneously 2 or 3 different interlaced messages, using quasi-crystals .SIGMA.(W.sub.1, V.sub.1), .SIGMA.(V.sub.1,V.sub.2), .SIGMA.(V.sub.2,W.sub.2). EXAMPLES 6 AND 7 In the first quasi-crystal example given hereinabove and shown in Table 1, the acceptance window has parameter W.sub.1 =0, W.sub.2 =1. The window of the subquasi-crystal may be chosen to be with parameters V.sub.1 =0.8, V.sub.2 =0.9. In the column denoted a+b.tau.' in Table 1, the points labeled by asterisks are in the window of the subquasi-crystal. In the second quasi-crystal example shown in Table 2, the acceptance window has parameters W.sub.1 =1988, W.sub.2 =2.6972. The window of the subquasi-crystal is chosen to be with parameters V.sub.1 =2.15, V.sub.2 =2.25. In the column denoted a+b.tau.', the points labeled by asterisks are in the window of the subquasi-crystal. Encryption transformation In the presently preferred embodiment, each point of the quasi-crystal is used to encrypt one 16-bit block of the original message (in fact, any value n could be used; to do so, simply replace 16 by n in the embodiment). The encryption is done as follows. For each generated point p.sub.i of the quasi-crystal, its corresponding color M(p.sub.i)=c.sub.i, is written in binary form as a 16-tuples of bits Y.sub.i. Instead of an aperiodic sequence of quasi-crystal points, an aperiodic sequence of 16-tuples of bits (colors) is obtained. In the presently preferred embodiment, the 16-tuples of bits from the colors are used directly during the encryption as the keystream, that is without bit insertions. Encryption is a rule how to compute from the n-tuple of the plaintext and an n-tuple of the keystream, an encrypted n-tuple. A possible encryption function is the standard exclusive-OR (xor) operation running simultaneously through the pairs consisting of one bit of the plain text and one bit of the keystream. The XOR operation is defined by the following formula: (0XOR 0)=(1XOR1)=0 (1XOR 0)=(0XOR1)=1 The security of the encryption is in the keystream and in the insertion of random bits. Therefore such as a simple (and fast) encryption function is adequate. In the simplest case the keystream is the sequence of colors of quasi-crystal points wherein in binary form. This is the case in the presently preferred embodiment. EXAMPLE 8 The keystream is composed from either the last or the third to last column of Table 1. The 4-tuple on each line is concatenated with the 4-tuple of the next line. The 4-tuples of lines 11 and 19, referring to the suquasi-crystal points, are preceded by random bits. XOR'ing a plaintext message with the keystream built above results in a ciphertest ready for transmission. The encrypted message is shown on the third line of Table 3.
TABLE 3
0101010101010101010101010101010101010101 01010101010101010101010101010101
01010101
0000011111101110010111001100001100111010r00010001100011111111011001101101r0
1000100
0101001010111011000010011001011001101111r01000100110110101010001100111000r0
0010001
The table shows encryption from Example 8 using the 20 points of Table 1 with coloring c.sub.1. The first line is a periodic plaintext. The second line is the keystream. The third line is the XOR of vertically aligned pairs from the lines one and two. Random bits are denoted r, they have no corresponding bits in the plaintext. EXAMPLE 9
TABLE 4
010101010101010101010101
0101010101010101010101010101010101010101010101010101 0101
110010110000010101001001r11010010000101101011101011111110001110000111110000
01r0000
100111100101000000011100r10000111010000111110111110101011011011010010101101
00r0101
The table shows encryption from Example 9 using 20 points of Table 2 with coloring c.sub.2. The first line is a periodic plaintext. The second line is the keystream. The third line is the XOR of vertically aligned pairs from the lines one and two. Random bits are denoted by r, they have no corresponding bits in the plaintext. In Table 4, the same plain text as in Example 7 is encrypted by the keystream built from the third to last column of Table 2. This keystream does not allow for the coloring parameters to be determined even if the plaintext consists of single characters repeated many times. The first (simpler) keystream of Table 3 is also usable for encryption provided the random bits are inserted into the encrypted text. Finally, the insertion of random bits into the encrypted message is done assuming that it is known which quasi-crystal points belong to the chosen subquasi-crystals .SIGMA.(V.sub.1, V.sub.2). Then the n-tuples of bits corresponding to these quasi-crystals points in the encrypted message is known. Before transmitting any such n-tuple, one inserts in front of it j random bits. The value of j can either be the part of the key or be fixed by the software or in hardware. Very small values of j are perfectly adequate. In Tables 1 and 2, the images of quasi-crystal points which fall into the window of the subquasi-crystal, are marked by an asterik. In Tables 3 and 4, the position of the inserted random bits is marked by r. Decryption In the presently preferred embodiment of a stream cipher, decryption is a task as demanding as encryption. The encryption function associates with several bits of the plain data several bits of the encrypted data (according to the details of the chosen setup). The function must be inevitable, which means that the this association can be read in the opposite direction. In the encryption examples XOR has been used together with the insertion of random bits as the encryption function/procedure. The receiver, knowing the key, generates the same quasi-crystal points, with the same precision as the transmitter, and with the same coloring, starting from the same seed point. It identifies the position of random bits during the generation of the quasi-crystal points and ignores them. It uses the inverse of the encrypting function to decode the bits of the encrypted data. In the examples given herein, the inverse function is again the same XOR operation. The simplicity of the XOR function as the encryption function is possible because of the quasi-crystalline properties of the keystreams. Such an encryption is also extremely fast. In Table 3 and 4, examples where words repeated in the plain message are encrypted differently are given. The encryption explained and illustrated above can be iterated several more times, using either the same or a new seed and/or quasi-crystal. Each subsequent level of encryption is independent of the previous one. In that the encrypted data at every level looks very different. The method according to the present invention is applicable to any sequence of digital data (bits) regardless of the message carried (text, voice, image, etc.). The quasi-crystals are known and can be efficiently generated in two-, three-, or more dimensions. In such an encryption, higher dimensional data do not need to be decomposed into a linear sequence of bits. At present, a practical limitation is the transmission technology and computing power. The present encryption method is directly extendable to higher dimensional data (see the section on watermarkings for discussion on 2-dimensional quasi-crystals). Combined with parallel processing, encryption of higher dimensional data is very effective. The aperiodic encryption method can be directly used for standard cryptographic applications: broadcast encryption and wireless telephony, video signal encryption, digital watermarking, electronic cash operations, etc. The minimal information which has to be conveyed, e.g. in the key, must be equivalent to the following: The irrationality on which the scheme is based; Boundaries of the acceptance window and the seed point; Coloring parameters (the actual number of parameters depends on the type of the coloring). Keystreams with greater complexity can be obtained by introducing further modifications to the generation of the basic keystream. The minimal key space is then enlarged by the range of the additional parameters. The modifications can come either from proven existing encryption methods, or they can be related to the properties of quasi-crystals. The modifications which the additional parameters would describe are, for example, the following ones: Insertion of random bits into the sequence; Use of two or more quasi-crystals for building up the keystream and the rules governing how to switch between them during the generation of the sequence, Coefficients of the encryption function which combines the plain text and the keystream; The number of times the encryption is repeated. Description of Block Cipher Embodiment Some current encryption practices known as block ciphers are based on the use a specified block size and a short encryption key which encrypts blocks of plaintext into blocks of ciphertext according to an encryption scheme. In most block ciphers, the encryption scheme is an n-step iteration process of a basic encryption scheme. With the knowledge of the decryption key and the block size, decryption can start from anyblock of the ciphertext. The block cipher embodiment can be provided using the fact that a given quasi-crystal can be generated from any of its points. For this, one needs to determine the size of the blocks and convey to the decryption end the coordinates of the quasi-crystal point which starts each block. This requirement can be achieved in a number of ways using software, the key or a simple convention (say a fixed number of points in each block) and within any of the three methods of generation of quasi-crystals mentioned above. For example, the encryption could be done as a simple modification of the stream cipher encryption described above. Assume the block size is set to b.sub.1 : 1. Divide the plaintext P in blocks of block size b.sub.1, that is P=P.sub.1 P.sub.2 P.sub.3 . . . , where P.sub.i are blocks of block size b.sub.1 ; 2. Generate the keystream K=K.sub.1 K.sub.2 K.sub.3 . . . , where K.sub.i are blocks of block size b.sub.1 ; 3. Specify a second block size b.sub.2 sufficiently large to contain the coordinates of a quasi-crystal point with sufficient precision. 4. After each block P.sub.1 of plaintext in P, insert a block B.sub.i+1 of block size b.sub.2 containing the coordinates of the quasi-crystal point corresponding (through coloring) to the first bit(s) of the block K.sub.i+1 in the keystream K, that is, P=P.sub.1 B.sub.2 P.sub.2 B.sub.3 P.sub.3 B.sub.4 . . . ; 5. The ciphertext C is then obtained by XOR'ing the corresponding P.sub.i and K.sub.i blocks, leaving the coordinate values non-encrypted. More precisely, C=C.sub.1 B.sub.2 C.sub.2 B.sub.3 C.sub.3 . . . , where C.sub.i =P.sub.i XOR K.sub.i. In this example, the decryption scheme makes use of the block size b.sub.1 and b.sub.2. To decrypt the ciphertext starting from block C.sub.1, one processes as for the stream cipher decryption, ignoring every block B.sub.i. To decrypt the ciphertext starting at block C.sub.i, one uses the (non-encrypted) value B.sub.i as the quasi-crystal seed point to generate the keystream and processes as for the stream cipher decryption, ignoring every block B.sub.i with j>i. Watermarking of Digital Documents Watermarking of an image, or an image of a document, means here a secret marking of the document in such a way that the presence of the mark can be demonstrated by the owner, who knows the watermarking key, but which otherwise cannot be detected. We assume for simplicity that all documents are 2-dimensional and that they are drawn on a lattice of points colored either by 0 or by 1 (white or black). Typically a document would consist of a large number of lattice points, often exceeding 10.sup.6. For 3- and higher dimensional `documents` an extension of the method is straightforward. The idea of the method is in exploiting quasi-crystal mapping (denoted by ') between a point x of a quasi-crystal .SIGMA.(.OMEGA.), and its image x' in the acceptance window .OMEGA.. Both the quasi-crystal and its acceptance window are now 2-dimensional. In order to keep the terminology intuitive, the acceptance window is called a sheet of paper. It can be of any size and form, and even made of several disconnected pieces. Important is only that its size is finite and that it has an non-empty interior. From the general theory, it can be shown that if the irrationally is chosen as before .tau.>1>.vertline..tau.'.vertline., say with .tau.=1/2(1+5) and .tau.'=1/2(1-5), then all the points with coordinates a+b.tau., where a and b are integers, will form a 2-dimensional quasi-crystal which is infinite and uniformity discrete and relatively dense. Prime (') is a one-to-one mapping between the quasi-crystal points and the points of .SIGMA.'(.OMEGA.) on the sheet of paper .OMEGA.. In the ideal case the sheet of paper is thus filled densely with the images x' of the infinitely many quasi-crystal points. Practically however, the finite precision of computers allows us to distinguish as different points of the paper, points which are at a distances not less than a certain minimal one. Thus even though the number of points on the sheet may be very large, practically it is always finite. If the sheet of paper contains only a finite number of points (the points of a lattice), then only a finite fragment of the quasi-crystal corresponds to it. The pertinent property of this mapping ' is that it is everywhere discontinuous, i.e. any two points which are close on one side of the map, are distant on the other side. Thus the closer the lattice points are on the paper, the farther apart the fragment corresponding to them will be, and vice versa. The watermarking of a document would use this property to mark a document by changing only a few non adjacent bits spread all over the document, bits which would then be mapped by onto a small region thus making a visible mark. An illustration of the discontinuity of the mapping ' is given in FIG. 4. For simplicity, all points of the quasi-crystal are colored black except 6 points which are all neighbors and colored white. The image of the quasi-crystal by the map ' covers densely the acceptance window, and since all but six points are colored in black, the acceptance window appears black. Magnifying the points in the acceptance window corresponding to white colored points of the quasi-crystal, it is clear that these points are not mapped in the same neighborhood. Moreover, infinitely many black colored points seperate any two white points. Finally, the position of any white point in the acceptance window does not give any information on the position of its image in the quasi-crystal. One of the watermarking possibilities is to place the digitized document which is to be marked in the sheet of paper .OMEGA. where the lattice points x' are situated. Its points are then identified with the points of a suitably chosen fine lattice on the paper. The color of the points of the document is taken to be the color of the points on the paper and also the color of the corresponding points of the quasi-crystal. The watermarking starts from the quasi-crystal fragment with points colored by the points of the digitized document which is to carry the watermark. The process then consists of the following: 1) choosing a subset of points of the colored quasi-crystal which will carry the watermark (in the simplest case these would be adjacent points forming a particular figure or shape); 2) marking the watermark by changing (if needed) the color of these points in a agreed prescribed way (for example making them all black); 3) mapping these points back to the paper while preserving the modified colors. The points of the watermark will be scattered over the document on the sheet of paper. Given the many points which form the document, the few with modified colors will be difficult to recognize. It is to be understood herein that the points to be changed are bits which are not considered to affect visual properties of an image, and which are easily wiped-out by image processing techniques and/or detectable as being watermark bits. Techniques are known in the art for applying watermarks to digital images and documents. Suitable techniques may be various forms of modulating the watermark information over large areas or hiding it in image boundaries, etc. The present invention may be used in conjunction with such techniques. Possible attacks on such a watermark: i) Point-by-point scanning of the documents with and without the watermark and comparing them will show the pints where the colors differ. It is always possible to choose the watermark in such a way that some points of the watermark may not have modified colors. Scanning and comparison approach will miss those points. ii) In order to decide what is the watermark (i.e. its shape), one would need to be able to find, for every point x' of the watermark, its quasi-crystal image x. However, that is possible only if one knows the absolute coordinates of the points x', i.e. relative to a chosen origin which can be way outside of the document during the design of the watermark. In order to prove that the a watermark is present, one needs to: a) know the exact position of the sheet of paper (i.e. coordinates of its points relative to some agreed origin); b) know the exact position of the document on the sheet of paper; c) know the position of the watermark in the quasi-crystal. The condition c) cannot be underestimated, because without it, in a typical case, there would be many tens of thousands of computer screens one would have to test for the presence of the watermark. There are important choices within this method which are to be made by the designer of the watermark such as the shape, size, position and color of the watermark. Another requirement is its robustness, more precisely the ability of the watermark to survive compression/decompression processes as well as other image processing techniques, as mentioned above. A simple way to form a 2-dimensional quasi-crystal is to start from two 1-dimensional quasi-crystals, each being oriented in some chosen direction in the plane (more about the orientation later). The desired quasi-crystal is the direct product of the two 1-dimensional quasi-crystal, i.e. every point of one of the quasi-crystals is combined with every point of the other. The acceptance window of such a 2-dimensional quasi-crystal is the direct product of the two acceptance windows of the 1-dimensional ones. Explicitly that is a rhombus if the 1-dimensional acceptance window were segments (i.e. connected). In general, one may need to work with quasi-crystals whose acceptance windows are of different shape than a given rhombus. For that, the new window is situated inside a suitably chosen rhombic one, and an additional test is performed on each quasi-crystal point, checking whether its image x' is not only in the rhombic window but also in the new window. Only in the case, the point x' is retained as the point of the new quasi-crystal. The relative orientation of the two 1-dimensional quasi-crystal, that one decides to use for the watermarking, has some implications which may be not only of practical importance. There are two issues one has to decide (choose): (i) relative orientation of the 1-dimensional quasi-crystal and (ii) what happens to their orientation when points x are mapped into x' or vice versa. The two choices can be made independently. Some possibilities will be explained with reference to three examples: I) The simplest choice would be to have the two quasi-crystal oriented perpendicularly to each other and perhaps even using, along each direction, the same 1-dimensional quasi-crystal. In the next two examples, the two 1-dimensional quasi-crystal are not orthogonally oriented. Their direction is given by two basis vectors, say i and j. The length and relative angles of the basis vectors are conveniently summarized in the matrix G of their scalar products: ##EQU10## where (i,j).sup.2 <(i,j)(j,j). Note that the example I) could be written in this form with (i,j)=0, The diagonal elements in G indicate the normalization of the basis vectors, more precisely they give their square length. The relative orientation of the vectors is the given by the value of the diagonal scalar product (i,j). A general point x of the quasi-crystal and its image x' are then respectively x=(a+b.tau.)i+(c+d.tau.)j, x'=(a+b.tau.')i'+(c+d.tau.')j', where a,b,c, and d are integers. The second issue above is the choice of the matrix G' for given G. ##EQU11## II) Mathematically appealing examples would be the ones where the two issues are resolved as follows: We choose the three scalar products in G having the values which can be written in the form p+q.tau., where p and q are some rational numbers such that the required inequalities (i,j).sup.2 <(i,j)(j,j) are verified. The matrix G' is then formed from G by replacing .tau. by .tau.' everywhere. III) Here G and G' are any symmetric matrices chosen independently and whose matrix elements satisfy the required inequalities. It will be appreciated that the present invention has been described hereinabove with reference to specific preferred embodiments, and that other embodiments are possible within the scope of the present invention, as defined in the appended claims. APPENDIX 1. Substitution rules for 1-dimensional cut and project tilings Here we describe the relation between substitution rules and 1-dimensional quasicrystals. We consider quasicrystals arising from the cut and project scheme with quadratic unitary Pisot numbers .beta.. For a quasicrystal .tau.(.OMEGA.) with a convex acceptance window .OMEGA., we prove that a substitution rule exists, precisely if .OMEGA. has boundary points in the corresponding quadratic held Q[.beta.]. In this case, one may find for arbitrary quasicrystal point x.epsilon..SIGMA.(.OMEGA.) a substitution generating the quasicrystal .SIGMA.(.OMEGA.) starting from x. We provide an algorithm for construction of such a substitution rule. 2. Introduction A substitution rule is an alphabet, together with a mapping which to each letter of the alphabet assigns a finite word in the alphabet. A fixed point of the substitution is an infinite word .omega. which is invariant with respect to the substitution. It can be studied from a combinatorial point of view (configurations of possible finite subwords), or from a geometrical point of view. In the later case we consider the letters of .omega. to be tiles of given length put in a prescribed order on the real line. In such a way, the tiling determines a Delone point set .LAMBDA..OR right.R. (A set .LAMBDA..OR right.R is said to satisfy the Delone property if it has uniform lower and upper bounds on the distances between adjacent points.) In order that the set .LAMBDA., obtained from the substitution, has a self-similarity, i.e. that there exists a factor s, that s .LAMBDA..OR right..LAMBDA., one has to choose the tiles to have suitable lengths. It is possible to extend the geometry of substitutions also to higher dimensions to construct for example tilings in the plane [9, 15]. In this paper we limit the consideration to substitution sequences which are 1-dimensional. Substitution rules may provide a wide variety of structures with different levels of order and randomness [1]. In particular, the substitution sequences may be both periodic or aperiodic. A standard way to construct quasiperiodic point sets is the `cut and project` method. One of the major applications of cut and project point sets is the modelling of physical quasicrystalline materials. The point sets obtained by the cut and project scheme, called here simply `quasicrystals`, have many remarkable properties. Among them especially the diffraction properties [10] and symmetries are of interest for quasicrystallographers. A very important attribute of cut and project sets is the presence of a rich structure of self-similarities [2,11]. A substitution rule carries a self-similarity factor for the corresponding Delone point set as a Perron-Frobenius eigenvalue of the substitution matrix. One may ask about the relation of cut and project quasicrystals and Delone sets generated by substitutions. In this paper we provide an answer to this question for large family of 1-dimensional quasicrystals. We decide about the existence of a substitution rule generating the given-quasicrystal, and if there exists one, we give a prescription how to find it. The connection of substitutive sequences to quasicrystals has been recognized for example by Bombieri and Taylor. In [5] they show that if the characteristic polynomial of the substitution rule is the minimal polynomial of a Pisot number, then the point set given by such a substitution is a subset of a cut and project set. The most frequently mentioned example of the Fibonacci chain constructed by the rule a.fwdarw.ab,b.fwdarw.a, is a 1-dimensional cut and project quasicrystal, see [5]. Gahler and Klitzing study the Fourier transform of Delone sets generated by substitution rules. They show in [8] that a substitution determines a set with non trival Bragg spectrum iff the largest eigenvalue of the substitution matrix (=scaling factor of the substitution tiling) is a Pisot number. In this article we study 1-dimensional cut and project sets based on the golden mean irrationality .tau.=1/2(1+5). However, our result can be extended for other quadratic unitary Pisot numbers as well. The algebraic definition of cut and project quasicrystals used in this paper (Definition 3.2) follows the analogy of [14]. A quasicrystal is a subset of the ring of integers Z[.tau.] of the quadratic field Q[5]. A point x.epsilon.Z[.tau.] belongs to the quasicrystal if its Galois conjugate x' lies in a chosen `acceptance interval` .OMEGA.. In order that a Delone set .LAMBDA..OR right.R with a finite number of tiles (distance between adjacent points) could be generated from a point x.epsilon..LAMBDA. by a substitution with the eigenvalue s, .LAMBDA. has to satisfy s(.LAMBDA.-x) .OR right..LAMBDA.-x. (Of course, it is not a sufficient condition for the existence of a substitution rule.) A cut and project quasicrystal .SIGMA. has the property that for any .epsilon..SIGMA. there are infinitely many different factors s, such that s(.epsilon.-x).OR right..SIGMA.-x. Such points x as centers of scaling symmetry are called s-inflation centers. A complete description of inflation centers is given in [11]. In this article we find necessary and sufficient condition on the acceptance interval .OMEGA. for the existence of a substitution rule which enables to generate the quasicrystal with the acceptance window .OMEGA., starting from a given point x of the quasicrystal. If this condition is satisfied, then for any quasicrystal point y there exists a substitution .theta..sub.y, depending on y, which generates the quasicrystal .SIGMA. from y. Note that the proof of this statement is constructive. We provide an algorithm for construction of the substitution rules for given .OMEGA. and y. 3. Preliminaries A substitution is a rule that assigns to each letter of an alphabet A a concatenation of letters, which is called a word. The set of words with letters in A is denoted by A*. An iteration of the substitution starting from a single initial letter leads to words of increasing length. Certain assumptions on the substitution rule ensure that the words give raise to an infinite sequence of letters which is invariant with respect to the substitution. DEFINITION 3.1 Let A be an alphabet. A map .theta.: A*.fwdarw.A* is called a substitution, if .theta.(a) is non empty for all a .epsilon. A and if it satisfies .theta.(.upsilon..omega.)=.theta.(.upsilon.).theta.(.omega.) for all .theta., .omega..epsilon.A*. An infinite sequence u .epsilon.A* is called a fixed point of .theta., if .theta.(u)=u. Let u be a fixed point of a substitution and .omega.: A.fwdarw.V be a mapping of the alphabet A into another alphabet V. The mapping .omega. can be extended into .omega.: A*.fwdarw.V*. The sequence .theta.=.omega.(u) is called the .omega.-image of u. If .theta.: A*.fwdarw.A* is a substitution and for a letter a .epsilon.A, one has .theta.(a)=a.omega. for some non empty word .omega..SIGMA.A*, then the sequence of word .theta..sup.n (a) converges to an infinite word u, which is a fixed pint of .theta.. We use the notation ##EQU12## Similarly, if there exists b .epsilon. A, such that .theta.(b)=.omega.b for some non empty .omega..epsilon.A*, we can construct a bidirectional infinite sequence starting the substitution rule from the pair b.vertline.a. As an example, let us mention the well known Fibonacci substitution rule .theta. on the alphabet formed by two letters, A={a, b}, given by a.vertline..fwdarw.ab, b.vertline..fwdarw.a. The second iteration of .theta. is a substitution a.vertline..fwdarw.aba b.vertline..fwdarw.ab (1) therefore we can generate from the pair b.vertline.a a bidirectional infinite word ##EQU13## We can associate lengths to letters a and b, and imagine the infinite sequence (2) as a labeling the tiles of a tiling of R. If we identify each tile with its left end point starting with the deliminator .vertline. at the origin, then we obtain a Delone point set .LAMBDA..OR right.R. Using for a and b the lengths determined by the standard analysis of the corresponding substitution matrix, the Delone set has a self-similarity s.LAMBDA..OR right..LAMBDA., where s is the dominant eigenvalue of the matrix. The suitable lengths of tiles are given as components of the eigenvector associated with s. Consider the substitution of (1). The corresponding matrix, its dominant eigenvalue and the associated eigenvector are given by ##EQU14## where .tau. is the golden mean irrationality. Setting the lengths l(a), l(b) to be .tau. and 1, it can be shown that the Delone set arising from the substitution coincides with a 1-dimensional cut and project quasicrystal. The definition is given below. Let .tau. and .tau.' be the roots of x.sup.2 =x+1, i.e. .tau..tau.'=-1 and .tau.+.tau.'=1. We have ##EQU15## Recall the ring of integers Z[.tau.]={a+b.tau..vertline.a, b .epsilon.Z} of the quadratic field Q[5] and the Galois automorphism ' defined by x'=(a+b.tau.)':=a+b.tau.'. DEFINITION 3.2 Let .OMEGA..OR right.R be a bounded interval with non empty interior. A cut and project quasicrystal is the set .SIGMA.(.OMEGA.):=(x.epsilon.Z[.tau.]x'.epsilon..OMEGA.). and .OMEGA. is called the acceptance window (interval) of the quasicrystal .SIGMA.(.OMEGA.). Let us formulate some of the properties of quasicrystals which will be used in this paper. Their proof is a direct consequence of the definition. It can be found for example in [4]. Note that for (v) one needs to know that .+-..tau..sup.k, k .epsilon.Z, are divisors of unity in the ring Z[.tau.], which ensures that Z[.tau.]=.tau..sup.k Z[.tau.]. LEMMA 3.3. Let .OMEGA..sub.1, .OMEGA..sub.2, and .OMEGA..OR right.R be intervals. Then (i) .SIGMA.(.OMEGA..sub.1).OR right..SIGMA.(.OMEGA..sub.2) if .OMEGA..sub.1 .OR right..OMEGA..sub.2, (ii) .SIGMA.(.OMEGA..sub.1).andgate..SIGMA.(.OMEGA..sub.2)=.SIGMA.(.OMEGA..sub. 1.andgate..OMEGA..sub.2), (iii) .SIGMA.(.OMEGA..sub.1).orgate..SIGMA.(.OMEGA..sub.2)=.SIGMA.(.OMEGA..sub. 1.orgate..OMEGA..sub.2), (iv) .SIGMA.(.OMEGA.)+.eta.=.SIGMA.(.OMEGA.+.eta.'), for any .eta..epsilon.Z [.tau.], (v) .tau..sup.k.SIGMA.(.OMEGA.)=.SIGMA.(.tau.'.sup.k.OMEGA.), for k .epsilon.Z, Consequently, we shall be interested only in quasicrystals with acceptance windows .OMEGA.=[c, d), such that 1.ltoreq.d-c<.tau.. If the length d-c of .OMEGA. is not within desired bounds, the property (v) of Proposition 3.3 allows us to find geometrically equivalent quasicrystal (rescaling the acceptance window properly), which satisfies the required condition. The restriction made on the interval to be semiclosed, [c, d), may influence only presence or absence of two particular points, namely c' and d' in the quasicrystal. This remark applies, of course, only if c, d belong to Z[.tau.]. Otherwise, including the boundary of the acceptance interval is not relevant for the quasicrystal. It is obvious that adding or removing a single point to a point set may strongly influence the form of the substitution rule. We deal with this problem in Section 7, providing examples of substitution rules for quasicrystal with closed and open acceptance windows. Construction of a substitution rule for a given quasicrystal .SIGMA.(.OMEGA.) from its particular point x.epsilon..SIGMA.(.OMEGA.) is, according to (iv) a Proposition 3.3, a task equivalent to finding a rule for .SIGMA.(.OMEGA.-x') starting from 0. Therefore we can limit ourselves for quasicrystals containing the origin, which gives us the conditions c.ltoreq.0, d>0, on the acceptance interval .OMEGA.=[c, d). Further important property of quasicrystals, which will be used in this paper, is formulated in the following proposition. Its proof can be found in [12]. PROPOSITION 3.4. Let .OMEGA. be an interval of length l, 1.gtoreq.l<.tau.. The distances between adjacent points of the quasicrystal .SIGMA.(.OMEGA.) are 1, .tau. and .tau..sup.2. We denote the distances 1, .tau. and .tau..sup.2 by S (=short), M(=middle) and L (=long) respectively. The letters will stand for both the tiles and their lengths. Following lemma allows to divide the elements of a given quasicrystal into three groups, according to tiles which follow them. The lemma is a straightforward consequence of Proposition 3.4. LEMMA 3.5. Let c, d .epsilon.R, 1.gtoreq.d-c<.tau.. The sets .SIGMA..sub.S, .SIGMA..sub.M and .SIGMA..sub.L of points of the quasicrystal .SIGMA.[c, d) which are followed be the distance 1, .tau., and .tau..sup.2 respectively, are given by ##EQU16## In particular, .SIGMA..sub.S is empty if d-c=1. 4. Construction of substitutions--idea and examples In this Section we explain the main ideas of the paper about the construction of a substitution for a given quasicrystal. We illustrate it on two examples. In the first of them (Example 4.1) we take the well known Fibonacci substitution and explain the fact that the corresponding Delone set is a cut and project quasicrystal. In the second Example 4.2, we start with a chosen quasicrystal and demonstrate the method how to find a substitution rule for it. A quasicrystal with tiles S, M, L is a bidirectional infinite word in these letters. Fixing a point in a quasicrystal corresponds to fixing the delimiter .vertline. between two particular letters of word. Construction of a substitution for such quasicrystal with respect to a chosen point stems in finding a rule .theta., such that the word of the quasicrystal with a given delimiter .vertline., is its fixed point. We show that only for a certain family of quasicrystals it is possible to find a substitution rule having the alphabet with three letters (S, M, L), (Proposition 6.2). For other quasicrystals, the tiles can be divided into groups S.sub.1, . . . , S.sub.k.sub..sub.s , M.sub.1, . . . , M.sub.k.sub..sub.M , and L.sub.1, . . . , L.sub.k.sub..sub.L . Then there exits a substitution .theta. with alphabet A=(S.sub.1, . . . , L.sub.k.sub..sub.L ) such that the quasicrystal is its fixed point. More formally, it is possible to find a substitution .theta. with an alphabet A and a mapping .omega.: A.fwdarw.(S, M, L) such that the quasicrystal is an .omega.-image of some fixed point of .theta.. We shall construct the substitution rule by dividing the short, middle and long distances into several groups in such a way that tiles in one group are, after rescaling by the factor .tau..sup.2, filled by the same sequence of distances. It is illustrated on FIG. 5. Determination of points followed by tiles of length S, M, or L consists, according to Lemma 3,5, in splitting the acceptance window of the quasicrystal into three disjoint subintervals. Similarly, determination of points followed by S.sub.1, . . . , S.sub.k.sub..sub.S , M.sub.1, . . . , M.sub.k.sub..sub.M , or L.sub.1, . . . , L.sub.k.sub.L corresponds to a splitting of the acceptance window .OMEGA. into k.sub.s +k.sub.M +k.sub.L disjoint intervals .OMEGA..sub.1, . . . .OMEGA..sub.k.sup..sup.L . We show that two quasicrystal points which have their ' image in the same subinterval .OMEGA..sub.i are, after rescaling by .tau..sup.2, followed by the same sequence of distances filling the corresponding tile S.sub.i, M.sub.i, or L.sub.i. The points determining the division .OMEGA. into .OMEGA..sub.i 's are called splitting points. We provide an explicite prescription for finding the splitting. It is obvious that if one has a substitution for a given quasicrystal and its point, then it is possible to find another substitution with larger alphabet for the same scaling factor. For example instead of a letter a we may write a.sub.1, a.sub.2 in a random order. Our division of .OMEGA. using splitting points provides a substitution rule with minimal alphabet for the scaling factor .tau..sup.2. It can be recognized from the form of the acceptance window .OMEGA., whether the set of splitting points is finite or infinite, see Proposition 5.9. If it is inifinite, then for a given quasicrystal a substitution rule with factor .tau..sup.2 does not exist. We show that then one cannot find neither a substitution with another scaling factor, (Theorem 5.10). If the set of splitting points is finite, we give an estimate on the number of letters of the alphabet, dependingly of the acceptance interval .OMEGA.. The size of the alphabet may be reduced using another factor, for example by iteration of the given substitution. This prolonges the word design to a single letter by the substitution. In Section 6 we describe those quasicrystals where a suitable iteration .theta..sup.P of a substitution rule .theta. with factor .tau..sup.2 gives a rule with 3-letter alphabet (S, M, L). EXAMPLE 4.1 Recall the Fibonacci substitution rule (1). Consider the letters a, b in its fixed point (2) to be tiles dividing the real axis. Set the length of the tile represented by a to be .tau..sup.2, and the length of the tile b to .tau.. Let us show that the tiling sequence ##EQU17## produces the quasicrystal .SIGMA.[-1/.tau..sup.2, 1/.tau.). The procedure is illustrated in FIG. 5. We shall use the self-similarity property (v) of Lemma 3.3, ##EQU18## The last inclusion is valid due to (i) of the lemma. All together this means that the quasicrystal point set rescaled with respect to 0 by the scaling factor .tau..sup.2 is subset of the original quasicrystal. The quasicrystal .SIGMA.[-1/.tau..sup.4, 1/.tau..sup.3) has the same ordering of tiles as .SIGMA.[-1/.tau..sup.2, 1/.tau.), but the lengths are .tau..sup.2 times rescaled, i.e. .tau..sup.4 and .tau..sup.3. The points of .SIGMA.[-1/.tau..sup.2, 1/.tau.) divide the tiles of .SIGMA.[-1/.tau..sup.4, 1/.tau..sup.3). Clearly, the rescaled tiles (lengths .tau..sup.4, .tau..sup.3) are divided into tiles of lengths .tau..sup.2 and .tau.. It is possible to do only in such a way, that .tau..sup.4 =2.tau..sup.2 +.tau. is cut into two of length .tau..sup.2 and one of length .tau., similarly the tile of length .tau..sup.3 splits into one of length .tau..sup.2, and one of length .tau. (recall that .tau..sup.3 =.tau..sup.2 +.tau.). Therefore the longer tile a after rescaling is replaced by the concatenation of twice a and b, the rescaled b becomes a concatenation of a and b. We will show that each of letters a are replaced by a, b, a in the same order, and similarly for the replacement of b, i.e. we will show that .SIGMA.(-1/.tau..sup.2, 1/.tau.) is generated by the substitution .theta.(a)=aba, .theta.(b)=ab. Note that the substitution .theta. is given by the action of several affine mappings. First, we rescale the points by the factor .tau..sup.2. It corresponds to the mapping t.sub.(1) x:=.tau..sup.2 x. Then we split the enlarged tiles by adding new points into them. Let x be followed by the tile a. The splitting of the enlarged tile with left end point .tau..sup.2 x according to .theta.(a)=aba means to insert new successors to the point .tau..sup.2 x, by mappings t.sub.(2) x:=.tau..sup.2 x+.tau..sup.2, t.sub.(3) x:=.tau..sup.2 x+.tau..sup.2 +.tau.. Let now y be followed by the tile b. The splitting of the rescaled tile b with the left end point being t.sub.(1) y=.tau..sup.2 y according to .theta.(b)=ab is done by adding one new point .tau..sub.(2) y:=.tau..sup.2 y+.tau..sup.2. Now it is important to decide, which quasicrystal points are left end points of tiles a with length .tau..sup.2, and which of them are left end points of tiles of the type b with length .tau.. Using Lemma 3.5 for the given quasicrystal .SIGMA.[-1/.tau..sup.2, 1/.tau.) we find that y .epsilon..SIGMA..sub.M =.SIGMA.[1/.tau..sup.3, 1/.tau.) are left end points of tiles b and x.epsilon..SIGMA..sub.L =.SIGMA.[-1/.tau..sup.2, 1/.tau..sup.3) are the left end points of tiles a. In order to show that the substitution .theta. generates our quasicrystal we have to prove that ##EQU19## Applying (iv) and (v) of Lemma 3.3, we obtain ##EQU20## The statement (iii) of Proposition 3.3 then gives us the result (3). In the previous example we have shown how the Fibonacci substitution (1) generates the 2-tile quasicrystal .SIGMA.[-1/.tau..sup.2, 1/.tau.). In the following example we find a substitution rule for the 3-tile quasicrystal .SIGMA.[0, 1+1/.tau..sup.2). Although the quasicrystal has only three types of tiles, we will use an alphabet formed by four letters. It will be clear that with the chosen scaling factor .tau..sup.2, one cannot find a substitution rule with smaller alphabet. EXAMPLE 4.2. Let us split the acceptance window .OMEGA.=[0, 1+1/.tau..sup.2) into intervals .OMEGA..sub.i i=1, . . . , 4 as follows. .OMEGA..sub.1 =[0, 1/.tau..sup.2), .OMEGA..sub.2 =[1/.tau..sup.2, 1/.tau.), .OMEGA..sub.3 =[1/.tau., 1), .OMEGA..sub.4 =[1,1+1/.tau..sup.2). Recall the sets .SIGMA..sub.S, .SIGMA..sub.L, and .SIGMA..sub.M of points followed by the tile S, M, L, respectively, (cf. Lemma 3.5). We have .SIGMA..sub.S =.SIGMA.(.OMEGA..sub.1), .SIGMA..sub.L.SIGMA.(.OMEGA..sub.2), .SIGMA..sub.M =.SIGMA.(.OMEGA..sub.3).orgate..SIGMA.(.OMEGA..sub.4). Let us assign the letters to intervals .OMEGA..sub.i, S to .OMEGA..sub.1, L to .OMEGA..sub.2, M.sub.1 to .OMEGA..sub.3, and M.sub.2 to .OMEGA..sub.4. In the construction of the substitution for our quasicrystal, we proceed in the following way: We stretch the quasicrystal by the factor .tau..sup.2 with respect to the origin. We obtain the quasicrystal .tau..sup.2.SIGMA.[0, 1+1/.tau..sup.2)=.SIGMA.[0, 1/.tau..sup.2, +1/.tau..sup.4) .OR right..SIGMA.[0,1+1/.tau..sup.2). The tiles of the stretched quasicrystal have lengths .tau..sup.2 times greater than S, M, L, namely .tau..sup.2, .tau..sup.3, and .tau..sup.4. Let us take the left end points y.sup.I of a stretched tile with length .tau..sup.2 S=.tau..sup.2. We shall look for right neighbours y.sup.II,y.sup.III, . . . of y.sup.I in .SIGMA.[0,1'+1/.tau..sup.2), which fill the corresponding tile .tau..sup.2 S. We have y.sup.I.epsilon..tau..sup.2.SIGMA.s. Therefore the ' image x=(y.sup.I)' belongs to 1/.tau..sup.2.OMEGA..sub.1. Since 1/.tau..sup.2.OMEGA..sub.1 .OR right..OMEGA..sub.1, the point y.sup.I belongs to .SIGMA..sub.S, and thus its smallest right neighbor in .SIGMA.(.OMEGA.) is the point y.sup.II =y.sup.I +S. Therefore (y.sup.II)'.epsilon.1/.tau..sup.2.OMEGA..sub.1 +1.OR right..OMEGA..sub.4. This means that y.sup.II .epsilon..SIGMA..sub.M. Its smallest right neighbour is y.sup.III =y.sup.II +M.sub.2. We have (y.sup.III)' .epsilon.1/.tau..sup.2.OMEGA..sub.1 +1-1/.tau..OR right.1/.tau..sup.2.OMEGA.. Thus y.sup.III is the right end point of the stretched tile .tau..sup.2 S. Symbolically it can be written as ##EQU21## We see that a stretched tile .tau..sup.2 S is filled by tiles S and M.sub.2, respectively. Formally, we have the rule S.fwdarw.SM.sub.2. Similarly we can proceed for left end points of other stretched tiles. It suffices to realize that the ' images of the left end points of stretched tiles .tau..sup.2 L belong to 1/.tau..sup.2.OMEGA..sub.2 =[1/.tau..sup.4, 1/.tau..sup.3). For left end points of .tau..sup.2 M.sub.1 we have 1/.tau..sup.2.OMEGA..sub.3 =[1/.tau..sup.3, 1/.tau..sup.2), and for .tau..sup.2 M.sub.2 we have 1/.tau..sup.2.OMEGA..sub.4 =[1/.tau..sup.2, 1/.tau..sup.2 +1/.tau..sup.4). The filling of the stretched tiles is schematically described by the following formulas and illustrated on FIG. 6. ##EQU22## Let us now make several comments to the table on FIG. 6. We can see that always the first and the last iterations of a given letter X, (X .epsilon.(S, L, M.sub.1, M.sub.2)), belong to 1/.tau..sup.2.OMEGA.. The second up to last iterations X.sup.II, X.sup.III, . . . of all letters together cover disjointly the entire acceptance window .OMEGA.. Note that the first iteration X.sup.I divide the interval 1/.tau..sup.2 .OMEGA. in a way different to the division by the last iteration of letters. The points of X.sup.I correspond to left end points of stretched tiles .tau..sup.2 X, and the points of last iterations correspond to right end points of the stretched tiles .tau..sup.2 X. Note that it was necessary to split M into M.sub.1 and M.sub.2, since points from M.sub.1.sup.I and M.sub.2.sup.I jump according to different prescriptions. 5. Justification of the method In the previous Section, we have explained on examples the steps which have to be done, in order to construct a substitution rule for a given quasicrystal. In this Section, we provide an algorithm for finding a suitable splitting of the acceptance window to groups of points which are assigned by the same letter. We shall justificate the procedure of construction of the substitution rules from such splittings, illustrated in Example 4.2. Throughout this Section, we shall consider the acceptance window .OMEGA.=[c, d), where c.gtoreq.0, d>0, 1.gtoreq.d-c<.tau.. Using Lemma 3.5 above, we are able to give a prescription, how to generate, one after another, the points of a quasicrystal. In each step we go from a point y .epsilon..SIGMA.[c, d) to its closest right neighbour in .SIGMA.[c, d). Considering the same procedures for ' images of points x=y' in the acceptance window, we may define a function .function.:.OMEGA..fwdarw..OMEGA. by ##EQU23## In this notation, the closest right neighbour of a quasicrystal point y is (.function.(y'))'. Generally, the k-th neighbour of y is (.function..sup.(k) (y'))'. Note that the function is in fact defined not only for numbers in Z [.tau.], but for all x.epsilon.[c, d). In that case the function .function. does not correspond to motion in the quasicrystal. If x.epsilon.Z [.tau.[, also .function.(x) belongs to Z[.tau.]. Moreover, if x.epsilon.1/qZ[.tau.], q .epsilon.N, also .function.(x) .epsilon.1/qZ [.tau.]. Whenever, x.epsilon.Q [.tau.], it means that its ' image x' is defined, we have x'+1.gtoreq.(.function.(x))'.gtoreq.'+.tau..sup.2. (5) Let us denote by Dense the quasicrystal Dense=.SIGMA.(.OMEGA.), and by Sparse its .tau..sup.2 -times enlarged copy Sparse=.tau..sup.2.SIGMA.(.OMEGA.)=.SIGMA.(1/.tau..sup.2.OMEGA.). Clearly, Sparse.OR right.Dense. Walking on points of Dense from left to right step-by-step, we come time to time to a point which belongs also to Sparse. Since the tiles in Dense are of lengths 1, .tau. and .tau..sup.2, and distances in Sparse are .tau..sup.2, .tau..sup.3, and .tau..sup.4 =3.tau.+2, the number of steps needed to move from one point of Sparse to another one is .ltoreq.5. On the other hand, any point y from Dense either belongs to Sparse, or we arrive to y from a point in Sparse after at most 4 steps. Since the corresponding motion in the acceptance window .OMEGA. is described by iterations of the function f, we can formulate previous transparent observations into the following propositions. Proposition 5.1. For any x.epsilon.1/.tau..sup.2.OMEGA. there exists a positive integer n(x).ltoreq.5, such that ##EQU24## Proposition 5.2. For any y.epsilon..OMEGA.1/.tau..sup.2.OMEGA. there exists a unique x.epsilon.1/.tau..sup.2.OMEGA., and a unique 0.ltoreq.i<n(x) such that f.sup.(i) (x)=y, The considerations carried before the formulation of the above propositions prove the assertions only for x, y.epsilon.Z[.tau.]. The proof for x, y.epsilon slash.Z[.tau.] follows from the fact that Z[.tau.].andgate..OMEGA. is dense in .OMEGA. and f is right continuous on .OMEGA.. The function f is bijective, therefore the inverse f.sup.(-1) is well defined. Thus for a given y.epsilon..OMEGA., the x from Proposition 5.2 can be found by iteration of f.sup.(-1). Let us define a function g:.OMEGA..fwdarw..OMEGA. by the prescription g(y):=.tau..sup.2 f.sup.(-1) (y), (6) where i is the minimal non negative integer such that f.sup.(-i) (y).epsilon.1/.tau..sup.2.OMEGA.. Note that 0.ltoreq.i.ltoreq.4, due to Propositions 5,1 and 5.2. Assume that we have a substitution rule with the scaling factor s, whose fixed point is the given quasicrystal .SIGMA.[.OMEGA.). The prescription of the substitution corresponds to filling of the tiles sS, sL, sM of the stretched quasicrystal s.SIGMA.[.OMEGA.), by the tiles of the original .SIGMA.[.OMEGA.), according to the function f. Consider two points x, y.epsilon..SIGMA.[.OMEGA.) followed by tiles which are assigned with the same letter, say a. It means that in an arbitrary iteration, say k-th, of the substitution, the s.sup.k times stretched tiles, following the points s.sup.k x and s.sup.k y are filled by the same sequence of distances. This implies that the iterations of the function f behave in the same way on points (s.sup.k x)', (s.sup.k y)'. It means that for any z.epsilon..SIGMA.[.OMEGA.), such that x'<z'<y', the function f behaves in the same way, and therefore we can assign the file following z by the letter a. Without loss of generality, we may assume that the points assigned to the same letter form an interval in .OMEGA..andgate.Z[.tau.]. The acceptance window .OMEGA. is split into a finite disjoint union of intervals, corresponding to letters of the alphabet. The above considerations lead us to the following definition. Definition 5.3. Let .alpha..sub.0, .alpha..sub.1, . . . , .alpha..sub.k be points such that c=.alpha..sub.0 <.alpha..sub.1 <. . . , .alpha..sub.k =d, and there exist k.sub.s, k.sub.L, 0.ltoreq.k.sub.s <k.sub.L <k, for which .alpha..sub.k.sub..sub.s =d-1 and .alpha..sub.k.sub..sub.L =c+1/.tau.. We denote by .OMEGA. the intervals .OMEGA..sub.i :=[.alpha..sub.i-1, .alpha..sub.i), i=1, . . . , k. The points .alpha..sub.i =0, . . . , k-1, are called the splitting points. We define a mapping .phi.:.OMEGA..fwdarw.A, where A is an alphabet A={a.sub.1, a.sub.2, . . . , a.sub.k }, by .phi.(x)=a.sub.i <.dbd.>x.epsilon..OMEGA..sub.i. Further, we define a mapping w:.OMEGA./.tau..sup.2.fwdarw.A*, which to any x.epsilon..OMEGA..sub.i /.tau..sup.2 associates the word w(x)=.phi.(z).phi.(f(x)).phi.(f.sup.(2) (x)) . . . .phi.(f.sup.(n(x)-1) (x)). We say that a splitting .OMEGA..sub.1, . . . , .OMEGA..sub.k, corresponding to splitting points .alpha..sub.0, .alpha.1, . . . , .alpha..sub.k-1, is proper, if the mapping w is constant on each .OMEGA..sub.i.tau..sup.2. The word w(x), common for all x.epsilon..OMEGA..sub.i /.tau..sup.2 is denoted by w.sub.1. A proper splitting defines naturally a substitution rule .zeta.: A.fwdarw.A* by .delta.(a.sub.i)=w.sub.1. Let as make several remarks to the definition above: Remark 5.4. 1. A splitting .OMEGA..sub.1, . . . , .OMEGA..sub.k is proper, if and only if for all 1.ltoreq.i.ltoreq.k, the following is true: For any x.epsilon..OMEGA./.tau..sup.2 there is a common value of n(x)=: n.sub.i, and there exist indices s.sub.0, s.sub.1, . . . , s.sub.ni-1 such that ##EQU25## For any 1.ltoreq.i.ltoreq.k, the interval .OMEGA..sub.i is a subset of either [c, d-1), or [c+1/.tau., d), or [d-1, c+1/.tau.). Thus the function f is continuous on each of the intervals .OMEGA..sub.i. It means that 1/.tau..sup.2.OMEGA..sub.i.OR right..OMEGA..sub.s.sub..sub.0 , being an interval implies that f(1/.tau..OMEGA..sub.i).OR right..OMEGA..sub.s.sub..sub.i is an interval. Similarly, images f.sup.(i) (1/.tau..sup.2.OMEGA..sub.i) of 1/.tau..sup.2.OMEGA..sub.i under all iterations of f are intervals. 3. Note that if 0 belongs to .OMEGA..sub.j.sub..sub.0 for some j.sub.0, then .PHI.(0)=a.sub.j.sub..sub.0 and therefore the word w(0) starts with a.sub.j.sub..sub.0 . Since 0 belongs also to the interval 1/.tau..sup.2.OMEGA..sub.j.sub..sub.0 , and w is constant on 1/.tau..sup.2.OMEGA..sub.j.sub..sub.0 , one has w(0)=w.sub.j.sub..sub.0 =.zeta.(a.sub.j.sub..sub.0 ). Similarly, let z=f.sup.(-1) (0), i.e. z' is the predecessor of 0 in Dense. Denote by i.sub.0 the index for which z.epsilon..OMEGA..sub.i.sub..sub.0 . Since f.sup.(n.sup..sub./0 .sup.-1) (tz/.tau..sup.2)=z, the word w(z)=w.sub.i.sub..sub.0 =.zeta.(a.sub.i.sub..sub.0 ) ends with a.sub.i.sub..sub.0 . Definition 5.5. We say that a substitution .theta. with the alphabet B={b.sub.1, . . . , b.sub.k } generates the quasicrystal .SIGMA.[c, d) from 0, if there exist indices i.sub.0, j.sub.0 .epsilon.{1, . . . , k}, such that ##EQU26## is a fixed point of the substitution .theta., and it is possible to assign lengths to letters b.sub.1, . . . , b.sub.k in such a way that the Delone set corresponding to the bidirectional infinite word ##EQU27## with the delimiter .vertline. fixed at the origin, is the quasicrystal .SIGMA.[c, d). Remark 5.6. Suppose that we have a proper splitting of the acceptance window .OMEGA.l. This splitting assigns the letters, say a.sub.j.sub..sub.0 , a.sub.i.sub..sub.0 , to the origin and its predecessor in the quasicrystal. According to point 3 of Remark 5.4, for the substitution .zeta. given by a proper splitting, we have .zeta.(a.sub.j.sub..sub.0 )=a.sub.j.sub..sub.0 w, for some w.epsilon.A*, and .zeta.(a.sub.i.sub..sub.0 )=wa.sub.i.sub..sub.0 , for some w.epsilon.A*. Therefore ##EQU28## is a fixed point of the substitution .zeta.. If we assign to letters a.sub.1, . . . , a.sub.k.sub..sub.s , the length l, to letters a.sub.k.sub..sub.s-1 , . . . , a.sub.k.sub..sub.L , the length .tau..sup.2, and to letters a.sub.k.sub..sub.L , . . . , a.sub.k, the length .tau., the fixed point is the quasicrystal .epsilon.(.OMEGA.). The entire quasicrystal Dense may arise by filling the distances in Sparse correctly (according to the function f) by tiles of Dense. It means that except of the points of Sparse, we take also a suitable number of their right neighbours in Dense. A point y of Sparse corresponds to x.epsilon.1/.tau..sup.2.OMEGA..andgate.Z[.tau.], where x=y'=f.sup.(0) (x). The neighbours of y correspond to points f(x), f.sup.(2) (x), . . . , f.sup.(n(x)-1) (x) in the acceptance window. Recall that the function n(x) is constant on the intervals 1/.tau..sup.2.OMEGA..sub.j of a proper splitting, i.e. we can denote n(x)=nj, for any x.epsilon.1/.tau..sup.2.OMEGA..sub.j. Therefore we have the disjoint union ##EQU29## From the right continuity of the function f, we may write also ##EQU30## where again the union is disjoint. According to point 1 of Remark 5.4, all splitting points are boundary points of some of the intervals f.sup.(i) (1/.tau..sup.2.OMEGA..sub.j). Let now the splitting point a, be a boundary of an interval f.sup.(i) (1/.tau..sup.2.OMEGA..sub.j)=[.alpha..sub.r, .epsilon.), for some 1.ltoreq.j.ltoreq.k and 0.ltoreq.i.ltoreq.n.sub.j -1. Then 1/.tau..sup.2 [.alpha..sub.j-1, .alpha..sub.j)=f.sup.(-i) [.alpha..sub.r, .zeta.), and hence .alpha..sub.j-1 =.tau..sup.2 f.sup.(-1) (.alpha..sub.r). Note that .tau..sup.2 f(.alpha..sub.r)(.alpha..sub.r)=g(.alpha..sub.r)=.alpha..sub.j-1, (7) where g was defined by (6). The following properties of g will be important. Remark 5.7. 1. For x.epsilon.Z[.tau.], g(x) is also in element of Z[.tau.], i.e. If x' .epsilon..SIGMA.(.OMEGA.), we have (g(x))' .epsilon..SIGMA.[.OMEGA.). 2. If x.epsilon.1/.tau..sup.2.OMEGA., then g(x)=.tau..sup.2 x. 3. g(c+1/.tau.)=g(c). 4. Note that the equation (7) says that the set of splitting points is invariant with respect to g. Proposition 5.8. Le | ||||||