Misplaced Pages

#141858

55-516: FCSRs have been used in the design of stream ciphers (such as the F-FCSR generator), in the cryptanalysis of the summation combiner stream cipher (the reason Goresky and Klapper invented them), and in generating pseudorandom numbers for quasi-Monte Carlo (under the name Multiply With Carry (MWC) generator - invented by Couture and L'Ecuyer,) generalizing work of Marsaglia and Zaman . FCSRs are analyzed using number theory . Associated with

110-416: A synchronous stream cipher a stream of pseudorandom digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used ( bits ), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher . In

165-463: A digit in the ciphertext, they might be able to make predictable changes to the corresponding plaintext bit; for example, flipping a bit in the ciphertext causes the same bit to be flipped in the plaintext. Another approach uses several of the previous N ciphertext digits to compute the keystream. Such schemes are known as self-synchronizing stream ciphers , asynchronous stream ciphers or ciphertext autokey ( CTAK ). The idea of self-synchronization

220-463: A digit is corrupted in transmission, rather than added or lost, only a single digit in the plaintext is affected and the error does not propagate to other parts of the message. This property is useful when the transmission error rate is high; however, it makes it less likely the error would be detected without further mechanisms. Moreover, because of this property, synchronous stream ciphers are very susceptible to active attacks : if an attacker can change

275-439: A digit is typically a bit and the combining operation is an exclusive-or (XOR). The pseudorandom keystream is typically generated serially from a random seed value using digital shift registers . The seed value serves as the cryptographic key for decrypting the ciphertext stream. Stream ciphers represent a different approach to symmetric encryption from block ciphers . Block ciphers operate on large blocks of digits with

330-417: A fixed, unvarying transformation. This distinction is not always clear-cut: in some modes of operation , a block cipher primitive is used in such a way that it acts effectively as a stream cipher. Stream ciphers typically execute at a higher speed than block ciphers and have lower hardware complexity. However, stream ciphers can be susceptible to security breaches (see stream cipher attacks ); for example, when

385-568: A given integer a that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes . No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order (its exponent ) of a number m modulo n is equal to φ ( n ) {\displaystyle \varphi (n)} (the order of Z {\displaystyle \mathbb {Z} } n ), then it

440-430: A non-linear filtering function . Instead of a linear driving device, one may use a nonlinear update function. For example, Klimov and Shamir proposed triangular functions ( T-functions ) with a single cycle on n-bit words. For a stream cipher to be secure, its keystream must have a large period , and it must be impossible to recover the cipher's key or internal state from the keystream. Cryptographers also demand that

495-450: A number g is a primitive root modulo  n if every number a coprime to n is congruent to a power of g modulo n . That is, g is a primitive root modulo   n if for every integer a coprime to n , there is some integer k for which g ≡ a (mod  n ). Such a value k is called the index or discrete logarithm of a to the base g modulo n . So g is a primitive root modulo   n if and only if g

550-462: A practical concern. For example, 64-bit block ciphers like DES can be used to generate a keystream in output feedback (OFB) mode. However, when not using full feedback, the resulting stream has a period of around 2 blocks on average; for many applications, the period is far too low. For example, if encryption is being performed at a rate of 8 megabytes per second, a stream of period 2 blocks will repeat after about an hour. Some applications using

605-399: A pseudorandom keystream which can be combined with the plaintext digits in a similar fashion to the one-time pad. However, this comes at a cost. The keystream is now pseudorandom and so is not truly random. The proof of security associated with the one-time pad no longer holds. It is quite possible for a stream cipher to be completely insecure. A stream cipher generates successive elements of

SECTION 10

#1732793303142

660-416: A secure wireless connection. If a block cipher (not operating in a stream cipher mode) were to be used in this type of application, the designer would need to choose either transmission efficiency or implementation complexity, since block ciphers cannot directly work on blocks shorter than their block size. For example, if a 128-bit block cipher received separate 32-bit bursts of plaintext, three quarters of

715-552: A simple quadratic polynomial involving the initial state and the q i . There is also an exponential representation of FCSRs: if g {\displaystyle g} is the inverse of N ( mod q ) {\displaystyle N{\pmod {q}}} , and the output sequence is strictly periodic, then a i = ( A g i mod q ) mod N {\displaystyle a_{i}=(Ag_{i}{\bmod {q}}){\bmod {N}}} , where A {\displaystyle A}

770-412: A synchronous stream cipher, the sender and receiver must be exactly in step for decryption to be successful. If digits are added or removed from the message during transmission, synchronisation is lost. To restore synchronisation, various offsets can be tried systematically to obtain the correct decryption. Another approach is to tag the ciphertext with markers at regular points in the output. If, however,

825-679: A variant of the Euclidean algorithm when N is prime; and in general by Xu's adaptation of the Berlekamp-Massey algorithm. If L is the size of the smallest FCSR that outputs the sequence (called the N-adic complexity of the sequence), then all these algorithms require a prefix of length about 2 L {\displaystyle 2L} to be successful and have quadratic time complexity. It follows that, as with LFSRs and linear complexity, any stream cipher whose N -adic complexity

880-596: Is 123 ≡ − 1 ≡ μ ( 31 − 1 ) ( mod 31 ) {\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}} . If a {\displaystyle a} is a primitive root modulo the prime p {\displaystyle p} , then a p − 1 2 ≡ − 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} . Artin's conjecture on primitive roots states that

935-640: Is a generator of the multiplicative group of integers modulo n . Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n . In fact, the Disquisitiones contains two proofs: The one in Article 54

990-416: Is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream ). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher . In practice,

1045-399: Is a 1, otherwise it repeats its previous output. This output is then (in some versions) combined with the output of a third LFSR clocked at a regular rate. The shrinking generator takes a different approach. Two LFSRs are used, both clocked regularly. If the output of the first LFSR is 1, the output of the second LFSR becomes the output of the generator. If the first LFSR outputs 0, however,

1100-2248: Is a nonconstructive existence proof , while the proof in Article 55 is constructive . A primitive root exists if and only if n is 1, 2, 4, p or 2 p , where p is an odd prime and k > 0 . For all other values of n the multiplicative group of integers modulo n is not cyclic . This was first proved by Gauss . The number 3 is a primitive root modulo 7 because 3 1 = 3 0 × 3 ≡ 1 × 3 = 3 ≡ 3 ( mod 7 ) 3 2 = 3 1 × 3 ≡ 3 × 3 = 9 ≡ 2 ( mod 7 ) 3 3 = 3 2 × 3 ≡ 2 × 3 = 6 ≡ 6 ( mod 7 ) 3 4 = 3 3 × 3 ≡ 6 × 3 = 18 ≡ 4 ( mod 7 ) 3 5 = 3 4 × 3 ≡ 4 × 3 = 12 ≡ 5 ( mod 7 ) 3 6 = 3 5 × 3 ≡ 5 × 3 = 15 ≡ 1 ( mod 7 ) {\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}} Here we see that

1155-533: Is a primitive root. In fact the converse is true: If m is a primitive root modulo n , then the multiplicative order of m is φ ( n ) = λ ( n )   . {\displaystyle \varphi (n)=\lambda (n)~.} We can use this to test a candidate m to see if it is primitive. For n > 1 {\displaystyle n>1} first, compute φ ( n )   . {\displaystyle \varphi (n)~.} Then determine

SECTION 20

#1732793303142

1210-417: Is an integer u {\displaystyle u} so that a = u / q {\displaystyle a=u/q} , a rational number. The output sequence is strictly periodic if and only if u {\displaystyle u} is between − q {\displaystyle -q} and 0 {\displaystyle 0} . It is possible to express u as

1265-583: Is an integer. It follows that the period is at most the order of N in the multiplicative group of units modulo q . This is maximized when q is prime and N is a primitive element modulo q . In this case, the period is q − 1 {\displaystyle q-1} . In this case the output sequence is called an l-sequence (for "long sequence"). l-sequences have many excellent statistical properties that make them candidates for use in applications, including near uniform distribution of sub-blocks, ideal arithmetic autocorrelations, and

1320-478: Is called the group of units modulo n , or the group of primitive classes modulo n . As explained in the article multiplicative group of integers modulo n , this multiplicative group ( Z {\displaystyle \mathbb {Z} } n ) is cyclic if and only if n is equal to 2, 4, p , or 2 p where p is a power of an odd prime number . When (and only when) this group Z {\displaystyle \mathbb {Z} } n

1375-517: Is cyclic, a generator of this cyclic group is called a primitive root modulo n (or in fuller language primitive root of unity modulo n , emphasizing its role as a fundamental solution of the roots of unity polynomial equations X − 1 in the ring Z {\displaystyle \mathbb {Z} } n ), or simply a primitive element of Z {\displaystyle \mathbb {Z} } n . When Z {\displaystyle \mathbb {Z} } n

1430-551: Is equal to since, in general, a cyclic group with r elements has φ ( r ) {\displaystyle \varphi (r)} generators. For prime n , this equals φ ( n − 1 ) {\displaystyle \varphi (n-1)} , and since n / φ ( n − 1 ) ∈ O ( log ⁡ log ⁡ n ) {\displaystyle n/\varphi (n-1)\in O(\log \log n)}

1485-404: Is insufficient to provide good security. Various schemes have been proposed to increase the security of LFSRs. Because LFSRs are inherently linear, one technique for removing the linearity is to feed the outputs of several parallel LFSRs into a non-linear Boolean function to form a combination generator . Various properties of such a combining function are critical for ensuring the security of

1540-434: Is low should not be used for cryptography. FCSRs and LFSRs are special cases of a very general algebraic construction of sequence generators called Algebraic Feedback Shift Registers (AFSRs) in which the integers are replaced by an arbitrary ring R and N is replaced by an arbitrary non-unit in R . A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book. Stream ciphers A stream cipher

1595-433: Is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below). For any n (whether or not Z {\displaystyle \mathbb {Z} } n is cyclic), the order of Z {\displaystyle \mathbb {Z} } n is given by Euler's totient function φ ( n ) (sequence A000010 in

1650-916: Is odd) is a primitive root modulo 2 p . Finding primitive roots modulo p is also equivalent to finding the roots of the ( p − 1)st cyclotomic polynomial modulo p . The least primitive root g p modulo p (in the range 1, 2, ..., p − 1 ) is generally small. Burgess (1962) proved that for every ε > 0 there is a C such that g p ≤ C p 1 4 + ε   . {\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.} Grosswald (1981) proved that if p > e e 24 ≈ 10 11504079571 {\displaystyle p>e^{e^{24}}\approx 10^{11504079571}} , then g p < p 0.499   . {\displaystyle g_{p}<p^{0.499}~.} Shoup (1990, 1992) proved, assuming

1705-474: Is often used in pseudorandom number generators and cryptography , including the Diffie–Hellman key exchange scheme. Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues . The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all

Feedback with Carry Shift Registers - Misplaced Pages Continue

1760-463: Is prime, then the period of repetition is n − 1. Permutations created in this way (and their circular shifts) have been shown to be Costas arrays . If n is a positive integer, the integers from 1 to n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n ) form a group , with multiplication modulo n as the operation; it is denoted by Z {\displaystyle \mathbb {Z} } n , and

1815-582: Is subject to strict security measures and fed to other devices such as a radio set, which will perform the XOR operation as part of their function. The latter device can then be designed and used in less stringent environments. ChaCha is becoming the most widely used stream cipher in software; others include: RC4 , A5/1 , A5/2 , Chameleon , FISH , Helix , ISAAC , MUGI , Panama , Phelix , Pike , Salsa20 , SEAL , SOBER , SOBER-128 , and WAKE . Primitive root modulo n In modular arithmetic ,

1870-485: Is the Möbius function . For example, E.g., the product of the latter primitive roots is 2 6 ⋅ 3 4 ⋅ 7 ⋅ 11 2 ⋅ 13 ⋅ 17 = 970377408 ≡ 1 ( mod 31 ) {\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}} , and their sum

1925-524: The OEIS ). And then, Euler's theorem says that a ≡ 1 (mod n ) for every a coprime to n ; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n . In particular, for a to be a primitive root modulo n , a has to be the smallest power of a that is congruent to 1 modulo n . For example, if n = 14 then the elements of Z {\displaystyle \mathbb {Z} } n are

1980-402: The generalized Riemann hypothesis , that g p = O(log p ). Fridlander (1949) and Salié (1950) proved that there is a positive constant C such that for infinitely many primes g p > C log p . It can be proved in an elementary manner that for any positive integer M there are infinitely many primes such that M < g p < p − M . A primitive root modulo n

2035-430: The period of 3 modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence ( g modulo  n ) always repeats after some value of k , since modulo  n produces a finite number of values. If g is a primitive root modulo  n and n

2090-627: The FCSR is a connection integer q = q r N r + ⋯ + q 1 N 1 − 1 {\displaystyle q=q_{r}N^{r}+\dots +q_{1}N^{1}-1} . Associated with the output sequence is the N-adic number a = a 0 + a 1 N + a 2 N 2 + … {\displaystyle a=a_{0}+a_{1}N+a_{2}N^{2}+\dots } The fundamental theorem of FCSRs says that there

2145-452: The arithmetic shift and add property. They are the with-carry analog of m-sequences or maximum length sequences . There are efficient algorithms for FCSR synthesis. This is the problem: given a prefix of a sequence, construct a minimal length FCSR that outputs the sequence. This can be solved with a variant of Mahler and De Weger's lattice based analysis of N-adic numbers when N = 2 {\displaystyle N=2} ; by

2200-489: The cipher but indicate that the cipher might have other weaknesses. Securely using a secure synchronous stream cipher requires that one never reuse the same keystream twice. That generally means a different nonce or key must be supplied to each invocation of the cipher. Application designers must also recognize that most stream ciphers provide not authenticity but privacy : encrypted messages may still have been modified in transit. Short periods for stream ciphers have been

2255-643: The congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ (15) = 8 of them. Since there is no number whose order is 8, there are no primitive roots modulo 15. Indeed, λ (15) = 4 , where λ is the Carmichael function . (sequence A002322 in the OEIS ) Numbers n {\displaystyle n} that have a primitive root are of the shape These are the numbers n {\displaystyle n} with φ ( n ) = λ ( n ) , {\displaystyle \varphi (n)=\lambda (n),} kept also in

Feedback with Carry Shift Registers - Misplaced Pages Continue

2310-406: The congruence classes {1, 3, 5, 9, 11, 13}; there are φ (14) = 6 of them. Here is a table of their powers modulo 14: The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14. For a second example let n = 15 . The elements of Z {\displaystyle \mathbb {Z} } 15 are

2365-403: The data transmitted would be padding . Block ciphers must be used in ciphertext stealing or residual block termination mode to avoid padding, while stream ciphers eliminate this issue by naturally operating on the smallest unit that can be transmitted (usually bytes). Another advantage of stream ciphers in military cryptography is that the cipher stream can be generated in a separate box that

2420-399: The different prime factors of φ ( n ) {\displaystyle \varphi (n)} , say p 1 , ..., p k . Finally, compute using a fast algorithm for modular exponentiation such as exponentiation by squaring . A number g for which these k results are all different from 1 is a primitive root. The number of primitive roots modulo n , if there are any,

2475-455: The generators are very common among {2, ..., n −1} and thus it is relatively easy to find one. If g is a primitive root modulo p , then g is also a primitive root modulo all powers p unless g ≡ 1 (mod p ); in that case, g + p is. If g is a primitive root modulo p , then g is also a primitive root modulo all smaller powers of p . If g is a primitive root modulo p , then either g or g + p (whichever one

2530-460: The keystream based on an internal state. This state is updated in essentially two ways: if the state changes independently of the plaintext or ciphertext messages, the cipher is classified as a synchronous stream cipher. By contrast, self-synchronising stream ciphers update their state based on previous plaintext or ciphertext digits. A system that incorporates the plaintext into the key is also known as an autokey cipher or autoclave cipher. In

2585-522: The keystream be free of even subtle biases that would let attackers distinguish a stream from random noise, and free of detectable relationships between keystreams that correspond to related keys or related cryptographic nonces . That should be true for all keys (there should be no weak keys ), even if the attacker can know or choose some plaintext or ciphertext . As with other attacks in cryptography, stream cipher attacks can be certificational so they are not necessarily practical ways to break

2640-399: The output of the second is discarded, and no bit is output by the generator. This mechanism suffers from timing attacks on the second generator, since the speed of the output is variable in a manner that depends on the second generator's state. This can be alleviated by buffering the output. Another approach to improving the security of an LFSR is to pass the entire state of a single LFSR into

2695-407: The registers decides which of the other two is to be used; for instance, if LFSR2 outputs a 0, LFSR0 is clocked, and if it outputs a 1, LFSR1 is clocked instead. The output is the exclusive OR of the last bit produced by LFSR0 and LFSR1. The initial state of the three LFSRs is the key. The stop-and-go generator (Beth and Piper, 1984) consists of two LFSRs. One LFSR is clocked if the output of a second

2750-547: The resultant scheme, for example, in order to avoid correlation attacks . Normally LFSRs are stepped regularly. One approach to introducing non-linearity is to have the LFSR clocked irregularly, controlled by the output of a second LFSR. Such generators include the stop-and-go generator , the alternating step generator and the shrinking generator . An alternating step generator comprises three LFSRs, which we will call LFSR0, LFSR1 and LFSR2 for convenience. The output of one of

2805-448: The same length as the plaintext and cannot be used more than once. This makes the system cumbersome to implement in many practical applications, and as a result the one-time pad has not been widely used, except for the most critical applications. Key generation, distribution and management are critical for those applications. A stream cipher makes use of a much smaller and more convenient key such as 128 bits. Based on this key, it generates

SECTION 50

#1732793303142

2860-462: The same starting state (seed) is used twice. Stream ciphers can be viewed as approximating the action of a proven unbreakable cipher, the one-time pad (OTP). A one-time pad uses a keystream of completely random digits. The keystream is combined with the plaintext digits one at a time to form the ciphertext. This system was proven to be secure by Claude E. Shannon in 1949. However, the keystream must be generated completely at random with at least

2915-443: The sequence A033948 in the OEIS . The following table lists the primitive roots modulo n up to n = 31 {\displaystyle n=31} : Gauss proved that for any prime number p (with the sole exception of p = 3), the product of its primitive roots is congruent to 1 modulo p . He also proved that for any prime number p , the sum of its primitive roots is congruent to μ ( p − 1) modulo p , where μ

2970-711: The stream cipher RC4 are attackable because of weaknesses in RC4's key setup routine; new applications should either avoid RC4 or make sure all keys are unique and ideally unrelated (such as generated by a well-seeded CSPRNG or a cryptographic hash function ) and that the first bytes of the keystream are discarded. The elements of stream ciphers are often much simpler to understand than block ciphers and are thus less likely to hide any accidental or malicious weaknesses. Stream ciphers are often used for their speed and simplicity of implementation in hardware, and in applications where plaintext comes in quantities of unknowable length like

3025-666: Was patented in 1946 and has the advantage that the receiver will automatically synchronise with the keystream generator after receiving N ciphertext digits, making it easier to recover if digits are dropped or added to the message stream. Single-digit errors are limited in their effect, affecting only up to N plaintext digits. An example of a self-synchronising stream cipher is a block cipher in cipher feedback (CFB) mode . Binary stream ciphers are often constructed using linear-feedback shift registers (LFSRs) because they can be easily implemented in hardware and can be readily analysed mathematically. The use of LFSRs on their own, however,

#141858