Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have been playing with base 26 LFSRs (i.e. using the alphabet) and noticed that the XOR operation for base 26 is just the tabula recta and so can be done very quickly. This made me wonder whether a base 26 LFSR (combined with a technique such as self shrinking) could be used as a PRNG that could be performed by hand and then XORed with the plaintext.

A base 26 LFSR would have to be of length 27 to have $\approx2^{128}$ possible states (giving 128 bit encryption?) but depending on the number of taps this could still be performed relatively quickly on paper.

I am not sure about my understanding of non-binary LFSRs so some of my assumptions may be incorrect but any help would be appreciated.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

LFSR theory, for an $n$-bit register uses an isomorphism between the shift operation, and the multiplication of a polynomial in $\mathbb{F}_2[X]$ by $X$; the multiplication is taken modulo a given polynomial $P$ of degree $n$; that modulus polynomial is the one defined by the position of the "feedback" bits and we usually want it to be primitive (i.e. irreducible, and such that $X$ generates, with the multiplication, all the non-zero polynomials modulo $P$). The XOR operation is, in fact, an addition of polynomials, i.e. a pairwise addition of monomials. In $\mathbb{F}_2$, values are bits and addition is XOR.

This extends to any finite field. But there is no finite field of size 26. What you can do is to map letters to integers modulo 26, and compute in the ring of such integers. By the Chinese Remainder Theorem, when you do arithmetic operations modulo 26, you are actually doing them in $\mathbb{F}_{13}$ and $\mathbb{F}_2$ simultaneously. So the theory can be applied through the CRT.

Namely, you could select a polynomial $P = X^n + \sum_{i=0}^{n-1} p_i X^i$ where each $p_i$ is equal to $0$ or $1$ (only), such that $P$ is primitive both in $\mathbb{F}_2$ and $\mathbb{F}_{13}$. The corresponding base-26 LFSR will then operate as the CRT mixture of a base-13 and a base-2 LFSR, of respective periods $13^n-1$ and $2^n-1$. Total period would be the least common multiple of these two values.

Notes :

  • Though LFSR have good statistical properties, for cryptography they tend not to be very good (e.g. you cannot keep the feedback polynomial $P$ secret, because of the Berlekemp-Massey algorithm). A secure LFSR-based stream cipher will need a trick, normally irregular clocking, as in A5/1. Resistance of A5/1 to cryptanalysis is roughly two thirds of its internal size (i.e. $2^{64·2/3}$) which is not high and allows for a lot of practical precomputations. For a "manual" LFSR, you may need to use a state size which will make it impractical. Also, the CRT duality can make analysis more complex. I suppose that a A5/1-like base-26 stream cipher can be designed and be secure, with a big enough internal state, but I don't have clear ideas on how big is "big enough".

  • You may have better luck using 32 signs (26 letters and some extra for spaces and punctuation). $\mathbb{F}_{32}$ is a field (not integers modulo 32, mind you; in $\mathbb{F}_{32}$, addition is indeed a XOR and each value, added to itself, yields a 0). However, you would also need a feedback polynomial where not all coefficients are $0$ or $1$ (otherwise you end up with running 5 binary LFSR in parallel). This can make the feedback rule application more complex.

  • A "manual" base-26 LFSR can be efficiently executed with a Scrabble game.

share|improve this answer
    
One could use 25 signs instead of 32 signs, so that one only needs letters. $\;$ –  Ricky Demer Oct 30 '13 at 23:15
    
The irregular clocking aspect would be taken care of by the self shrinking LFSR. I am not entirely sure how you would "compute in the ring of such integers", was this not what I was doing with addition mod 26? –  Scytheon3 Oct 31 '13 at 13:14
    
The ring of integers modulo 26 is exactly the set of integers in the 0..25 range with addition and multiplication modulo 26. –  Thomas Pornin Oct 31 '13 at 13:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.