> the first 70 bits of the key, are the first 70 bits out of hte LFSR
> starting from position 0?

The first 70 bits should correspond to the first 10 characters in the 
ciphertext, not the 10 ciphertext characters after the start of the crib.

> under hw5 notes on your website the are two different ways of using the
> tabs and s[i].
>  
> lets say you have
>  
> s 0 1 0 0 1
> c 1 0 1 0 1
>  
> at time t,
>  
> what will be the next time
> do you go back or foward .
> if back you would        1 0 0 1 _   with output 0
> or foward                _ 0 1 0 0   with output 1

It depends on what you're doing.

If you go forward (normal keystream generation), then you shift right, and
fill the hole on the left:
  
  s 1 0 1 0 0 (time t+1)

If you're trying to go back in time to recover the initial conditions of
the LFSR, then you shift left, and fill in the hole to the right:
  
  s 1 0 0 1 1 (time t-1)

> homework we have to do.  I am still curious though about what exactly to do 
> with the output spit out by the shift register and which index exactly we 
> are supposed to XOR it with in the ciphertext.  

The output of the LFSR, if everything is correct, represents the keystream 
that you XOR with the plaintext to get the ciphertext.

But remember that all of the following are true:

  Y = X XOR K
  X = Y XOR K
  K = X XOR Y

where K is the keystream.  So you can simply take the keystream and XOR 
with the ciphertext to recover the plaintext.  The first thing to do is 
generate 7 bits of keystream.  Do a bitwise XOR with the ciphertext 
character at the position of your inner j loop (just inside the outer N, 
or width, loop).  This should get you the first character of your crib.  
(See page 17, with the binary representations of keystream, cipher-, and 
plaintext, for an example of how the bits should "line up".)

Continue the above, generating 7 bits of keystream per character, until 
you are sure that this is generating printable ASCII (you will want to go 
for at least 6 characters).

> How do we work backwards to 
> find parts of the key ( previously popped off bits) before our initial 
> values of s?


  S  1 0 0 0 1 (time t)
  C  1 0 1 1 1

First you shift everything backwards, leaving a hole on the right:

  S  0 0 0 1 _ (time t-1)

Then you fill in the hole with the result of the same feedback eqn

  f = S4C1 + S3C2 + S2C3 + S1C4 + S0C5

The taps are the same

  f = S4*1 + S3*0 + S2*1 + S1*1 + S0*1

Fill in what you know, leaving the blank at S0

  1 =  0*1 +  0*0 +  0*1 +  1*1 + S0*1
  
Solve for S0.

  1 = 1 + S0
  S0 = 0

  S  0 0 0 1 0 (time t-1)

In office hours I did another example:

  S  0 0 0 0 1
  C  1 0 1 1 1

 t-1 0 0 0 1 1
 t-2 0 0 1 1 0

See also http://www.cs.ucsb.edu/~kirbysdl/cs178/homework5.html

From: Ted Huffmire 

> I am able to decipher everything and now  need to figure out the degree of
> the generating polynomial, and the coefficients of the generating
> polynomial.
> 
> question 1: are the coefficients of the generating polynomial just my
> taps? (which
> are permanent)
>

yes
 
> question 2: on page 10-11 of the reader Konheim explains the degree of the
> generating polynomial but I am still confused.
> 

the degree of the characteristic polynomial is the number
of registers - 1.

> Okay so I have my taps and it seems that the P(z) equation is just which
> taps are on or off starting with 1 on the right side of the LFSR and n-1
> on the left hand side. Now how to I compute my degree? Is my entire idea
> for part 2 wrong?
> 
> Thanks!!!!

I don't think you need P(z) to accomplish part 2.
The equation you need is the recurrence relation (1d) for 
forward recursion and (1e) for backward recursion. 
These are located on page 4.

> i'm using the formula    A'S=Cwhere A' is the inverse matrix and S is our S 
> matrix so when i do the multiplication for some of my c[i] value the numbers 
> are more then 1 since i'm adding it. What do i need to do. Do i need to %2 
> the value i get or what? i'm having trouble getting the C value knowing the 
> original A and S matrices can you help me pleasethanks alex

From: Ted Huffmire 

If you know A and S, you can easily
determine the values of c. For example:
(1)   (1 0 1)(c1)
(0) = (0 1 0)(c2)
(1)   (0 0 1)(c3)

c1 + c3 = 1
c2 = 0
c3 = 1

Therefore c1 = 0

From: Michael S. Lee 

Yeah, whenever you might get a value greater than 1, do a mod 2.

See also http://www.cs.ucsb.edu/~konheim/CS178/CribGauss.pdf

> I'm working on my program and i first converted all the numbers into 7 digit 
> binaries, creating an array of 9940 1/0s.
> 
> then i have a loop that goes for N1 (6) to N2 (9) with a loop from j1 (0) to 
> j2 (n) nested inside it. Then i'm suppose to create the gamme(7j, N) matrix. 
> How do i create that matrix from my position?

Yeah you can refer to the reader, and also the the pdfs on the cs178 class 
website.  In general, what you will be doing is XORing your crib with the 
ciphertext at the position under consideration.  From that, you will get 
the s0, s1, s2, ... bits that you need to fill in the matrices.

After building the matrices, solve for the taps.  Having the taps, 
generate some keystream, XOR with the ciphertext to make sure you are 
getting printable ascii.  

If anything goes wrong along the way (and your program is correct) then 
you know you have the wrong position or width, so then continue with the 
next width/position combination until you get the right answer.

> Ok, I have gotten down to the Gaussian elimination.  I have 
> solved the equations and am now a little confused as to what I am
> supposed to do.  Let's say I am working on N=6.  Do I try all 
> binary numbers from 0-32 as the start state, XOR-ing them with my
> tapped location, XOR that with the ciphertext and then look for 
> the plaintext?  I am confused as to exactly how you use the s, c,
> x, and y.. Can you please explain the steps that follow solving 
> for the c values?  I would really appreciate it, thank you

At this point you have enough information to unambiguously recreate the 
LFSR.  You solved for your taps c_i, you assumed a width N, and you 
already know the initial cell contents s_i.  Without that knowledge, you 
wouldn't have been able to generate the matrices for Gaussian.

See in the reader (for example on page 17) where it has s_0, s_1, etc. as 
the matrix elements?  Those are the state bits you'll be using in your 
LFSR!  Just plug them in as shown on page 1 of CRIB-LFSR.pdf and you'll be 
fine.

If you're wondering how the taps and state bits interact, think of the 
following:

  -----------
S |0 1 1 0 1|
  -----------
C  1 1 0 0 1 

You don't XOR, but rather multiply corresponding s and c bits, so:

   0 1 0 0 1

Then you XOR those bits (or add them modulo 2) to get the feedback bit.

   0+1+0+0+1 = 0 (mod 2)

Then you shift everything over by one, and fill in the feedback bit

  -----------
S |0 0 1 1 0|1
  -----------

The bit that just popped off the end is your output.

Do that seven times for 7 bits of keystream (enough for a single 
ciphertext char), etc.etc.

>    I am confused at how we are supposed to get the initial 2N keystream for 
> the matrix.  I know that we are supposed to XOR the ciphertext ordinals with 
> the plaintext ordinals, but which plaintext do we use?  Do we use the two 
> column plain text that is in hw5ci, and are we supposed to use it in the 
> order it is shown there?  For example, if I were to use the first person as 
> the crib (0.  Allen, Stuart) would I XOR all the ordinals derived from 
> Stuart Allen's name and identifier number (and spaces) with the first equal 
> amount of ordinals of the ciphertext?  Any help on this matter would be 
> appreciated.

The plaintext is the crib.  The ciphertext is hw5ci.  You can choose 
whatever you want for the crib.  The first name shown on the first page of 
the homework handout is not necessarily the first entry in the plaintext 
before he enciphers (read the homework carefully to see why).  For a 
bit-by-bit example of how to get keystream, look at page 17 of the reader 
(stream ciphers chapter).