How do you cryptanalyze two XORed LFSRs?
On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research <cascares@yahoo.com> wrote:
How do you cryptanalyze two XORed LFSRs?
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve
that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
If you want a more specific answer, you'll have to ask a more specific question.
--
To email me, substitute nowhere->runbox, invalid->com.
On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote:[snip]
On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research wrote:
How do you cryptanalyze two XORed LFSRs?
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve
that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
If you want a more specific answer, you'll have to ask a more specific
question.
You mean one equation per one bit of the LFSR? What do those equations
look like?
On Sun, 9 Apr 2017 06:58:09 -0700 (PDT), Cascade Research wrote:
On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote:[snip]
On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research wrote:
How do you cryptanalyze two XORed LFSRs?
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve
that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
If you want a more specific answer, you'll have to ask a more specific
question.
You mean one equation per one bit of the LFSR? What do those equations
look like?
If we designate one particular moment as time t=0, and name the
unknown contents of LFSRs A and B at that moment as a0, a1, ...
and b0, b1, ..., and if we know that a certain number of
LFSR steps later the XORed outputs of A and B give the value z,
then we get an equation of the form
z = ca0 * a0 + ca1 * a1 + . . . + cb0 * b0 + cb1 * b1 + . . .
where the coefficients ca0, cb0, et cetera, can be computed from the definition of the LFSRs (but not their contents, obviously) and the
number of steps. In these equations, "*" means logical AND and "+"
means XOR, but solving the equations works absolutely the same as what
you learned in high school because "*" and "+" still have all the
properties (commutative, associative, distributive, et cetera) that make
that solution work.
I wrote an article on this that was published in Cryptologia volume 12,
1988.
--
To email me, substitute nowhere->runbox, invalid->com.
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
On Sun, 9 Apr 2017 06:58:09 -0700 (PDT), Cascade Research wrote:
On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote:[snip]
On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research wrote:
How do you cryptanalyze two XORed LFSRs?
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve
that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
If you want a more specific answer, you'll have to ask a more specific
question.
You mean one equation per one bit of the LFSR? What do those equations
look like?
If we designate one particular moment as time t=0, and name the
unknown contents of LFSRs A and B at that moment as a0, a1, ...
and b0, b1, ..., and if we know that a certain number of
LFSR steps later the XORed outputs of A and B give the value z,
then we get an equation of the form
z = ca0 * a0 + ca1 * a1 + . . . + cb0 * b0 + cb1 * b1 + . . .
where the coefficients ca0, cb0, et cetera, can be computed from the
definition of the LFSRs (but not their contents, obviously) and the
number of steps. In these equations, "*" means logical AND and "+"
means XOR, but solving the equations works absolutely the same as what
you learned in high school because "*" and "+" still have all the
properties (commutative, associative, distributive, et cetera) that make
that solution work.
I wrote an article on this that was published in Cryptologia volume 12,
1988.
--
To email me, substitute nowhere->runbox, invalid->com.
OK, do you have a URL or PDF?
On Wed, 12 Apr 2017 16:06:57 -0700 (PDT), Cascade Research wrote:
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
On Sun, 9 Apr 2017 06:58:09 -0700 (PDT), Cascade Research wrote:
On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote: >>> >> On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research wrote:[snip]
How do you cryptanalyze two XORed LFSRs?
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve >>> >> that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
If you want a more specific answer, you'll have to ask a more specific >>> >> question.
You mean one equation per one bit of the LFSR? What do those equations >>> > look like?
If we designate one particular moment as time t=0, and name the
unknown contents of LFSRs A and B at that moment as a0, a1, ...
and b0, b1, ..., and if we know that a certain number of
LFSR steps later the XORed outputs of A and B give the value z,
then we get an equation of the form
z = ca0 * a0 + ca1 * a1 + . . . + cb0 * b0 + cb1 * b1 + . . .
where the coefficients ca0, cb0, et cetera, can be computed from the
definition of the LFSRs (but not their contents, obviously) and the
number of steps. In these equations, "*" means logical AND and "+"
means XOR, but solving the equations works absolutely the same as what
you learned in high school because "*" and "+" still have all the
properties (commutative, associative, distributive, et cetera) that make >>> that solution work.
I wrote an article on this that was published in Cryptologia volume 12,
1988.
--
To email me, substitute nowhere->runbox, invalid->com.
OK, do you have a URL or PDF?
Are you kidding? This was 1988; I had to submit the manuscript
on paper.
Take your pick: I can send you the files that I printed on whatever
printer I had in 1988 to generate the manuscript I mailed to Cryptologia
(the files are almost entirely ASCII, with a few escape sequences for superscripts and subscripts), or you can email me your postal address
and I'll mail you a genuine paper reprint. (Yes, I still have several.)
On Wed, 12 Apr 2017 16:06:57 -0700 (PDT), Cascade Research wrote:
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
On Sun, 9 Apr 2017 06:58:09 -0700 (PDT), Cascade Research wrote:
On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote: >> >> On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research wrote:[snip]
How do you cryptanalyze two XORed LFSRs?
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve >> >> that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
If you want a more specific answer, you'll have to ask a more specific >> >> question.
You mean one equation per one bit of the LFSR? What do those equations >> > look like?
If we designate one particular moment as time t=0, and name the
unknown contents of LFSRs A and B at that moment as a0, a1, ...
and b0, b1, ..., and if we know that a certain number of
LFSR steps later the XORed outputs of A and B give the value z,
then we get an equation of the form
z = ca0 * a0 + ca1 * a1 + . . . + cb0 * b0 + cb1 * b1 + . . .
where the coefficients ca0, cb0, et cetera, can be computed from the
definition of the LFSRs (but not their contents, obviously) and the
number of steps. In these equations, "*" means logical AND and "+"
means XOR, but solving the equations works absolutely the same as what
you learned in high school because "*" and "+" still have all the
properties (commutative, associative, distributive, et cetera) that make >> that solution work.
I wrote an article on this that was published in Cryptologia volume 12,
1988.
--
To email me, substitute nowhere->runbox, invalid->com.
OK, do you have a URL or PDF?
Are you kidding? This was 1988; I had to submit the manuscript
on paper.
Take your pick: I can send you the files that I printed on whatever
printer I had in 1988 to generate the manuscript I mailed to Cryptologia
(the files are almost entirely ASCII, with a few escape sequences for superscripts and subscripts), or you can email me your postal address
and I'll mail you a genuine paper reprint. (Yes, I still have several.)
--
To email me, substitute nowhere->runbox, invalid->com.
Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve
that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 296 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 24:39:06 |
| Calls: | 6,646 |
| Calls today: | 1 |
| Files: | 12,193 |
| Messages: | 5,327,716 |