CoCalc Shared FilesCrypto_Fall_17 / project_2 / lfsr.c
Authors: Hunter Johnson, Kristy Li
1/*
2Code for 64 bit LFSR
3Hunter Johnson
49/15/17
5*/
6
7#include <iostream>
8#include <stdint.h>
9#include <stdlib.h>
10#include <stdio.h>
11#include <assert.h>
12
13using namespace std;
14
15/*The following struct will represent an LFSR with a 64 bit state.
16  The taps are represented by a 64 bit number, where the ith bit (from the right)
17  corresponds to p_i (in the notation of the textbook).
18  The uint64_t is a 64 bit unsigned integer.
19  There is a small chance that this code may behave unexpectedly if compiled on Windows or Mac.
20  Please let me know if you get issues.
21  It compiles and runs under clang and gcc. */
22
23typedef struct {
24	uint64_t state;
25	uint64_t taps;
26} LFSR;
27
28int parity(uint64_t N)
29{
30/* Return the parity of N*/
31	int p = __builtin_parity(N); // parity of first 32 bits
32	N = __builtin_bswap64(N); //move back 32 to the front
33	return (p+__builtin_parity(N))%2; //overall parity
34}
35
37{
38/*Return the current output bit (the rightmost bit of the state variable) */
39    uint64_t rightMostBit = L->state &1;
40    return rightMostBit;
41}
42
43void next_state(LFSR* L)
44{
45    uint64_t next_bit = parity(L->state & L->taps);
46    L-> state = L->state >> 1;
47    L->state = L->state | (next_bit << 63);
48}
49
50void init_LFSR(LFSR* L, uint64_t initial_state, uint64_t taps)
51{
52/*Initialize with state and taps*/
53	L->state = initial_state;
54	L->taps = taps;
55}
56
57unsigned char get_stream_byte(LFSR* L)
58{
59/*Return one byte of keystream.
60  Note that the byte fills up from left to right.
61*/
62	unsigned char C = 0;
63	int i = 7;
64	for(;i>=0;i--)
65	{
68		next_state(L);
69	}
70	//printf("\t%d\n",C);
71	return C;
72}
73
74void encrypt(const char* pt, const char* ct,LFSR *L)
75{
76/*Use the LFSR stream cipher to encrypt
77  the file named pt (plaintext) and write the
78  output to the file named ct (ciphertext);
79*/
80	FILE* PT = fopen(pt,"r");
81	FILE* CT = fopen(ct,"w");
82	assert(PT); //make sure files opened okay
83	assert(CT);
84	int c;
85	while((c=getc(PT))!=-1)
86	{
87		unsigned char sb = get_stream_byte(L);
88		fputc(sb^c,CT);
89	}
90	fclose(PT);
91	fclose(CT);
92}
93
94void decrypt(const char* pt, const char* ct,LFSR *L)
95{
96/*Make sure L has been reset to the initial state*/
97    uint64_t initial_state;
98    L->state = initial_state;
99	encrypt(pt,ct,L);
100}
101
102void get_128_keystream_bits(const char* ct, const char* kpt)
103{
104  /*This function takes 16 bytes of ciphertext and 16 bytes of
105  known plaintext.
106  The output is a file named "key_stream.txt" that contains 128 bits
107  of keystream.  The stream is represented in ASCII, with 128 lines, and
108  either a "0" or a "1" on each line.*/
109	FILE* ct_f = fopen(ct,"r");
110	FILE* fp = fopen("key_stream.txt","w");
111    FILE* fs = fopen("key.txt","w");
112 	int i = 0;
113	for(;i<16;i++)  //16 bytes
114	{
115		unsigned char ctc = getc(ct_f);
116		unsigned char b = ctc^kpt[i];  //the current byte
117        int j = 7;
118        for(;j>= 0;j--)
119        {
120            char current_bit = parity(b&(1 << j));
121            fprintf(fp, "%u\n", current_bit);
122            fprintf(fs, "%u", current_bit);
123           // int bit = parity(b & (1<<j));
124           // fprintf(fp,"%d\n",bit);
125        }
126	}
127	fclose(fp);
128	fclose(ct_f);
129}
130
131void shape_keystream()
132{
133/* This function opens the file "key_stream.txt" created by
134   get_128_keystream_bits().  It uses this data to create a file called
135   "S.mat.sage" which is a 64x64 matrix of keystream bits of the form
136    discussed in the project description. It also creates a vector
137    (a 64x1 matrix) of keystream bits of the form described in the
138    project description.  This is stored in a file called "V.mat.sage" */
139	FILE* fp = fopen("key_stream.txt","r");
140	FILE* VS = fopen("V.mat.sage","w");
141	FILE* SS = fopen("S.mat.sage","w");
142
143	assert(fp);
144    assert(SS);
145    assert(VS);
146
147    int buffer[128];
148
149    for(int i = 0; i < 128; i++)
150    {
151        fscanf(fp, "%d", &buffer[i]);
152    }
153
154    fprintf(SS, "A = matrix(Zmod(2),[[");
155
156    for(int i = 0; i < 64; i++)
157    {
158        for(int j = 0; j < 64; j++)
159        {
160           if(i  + j < 127 && j < 63)
161                fprintf(SS, "%d,", buffer[i + j]);
162            else
163                fprintf(SS, "%d", buffer[i + j]);
164       }
165       if (i < 63)
166       {
167           fprintf(SS, "],\n[");
168       }
169    }
170
171    fprintf(SS, "]])\n");
172
173   fprintf(VS, "x = vector(Zmod(2),[");
174   for(int i = 64; i < 128; i++)
175   {
176       fprintf(VS, "%d", buffer[i]);
177       if (i < 127)
178       {
179           fprintf(VS, ",");
180       }
181       else
182           fprintf(VS, "])");
183   }
184
185	fclose(fp);
186	fclose(SS);
187	fclose(VS);
188}
189
190int main()
191{
192	LFSR L;
193	uint64_t initial_state = 0xc2d075d0518516e9L; //0xC29711548D9DECDF;//0xFB37B9B12A88E943;
194	uint64_t taps = 0x578140d19a35c76c;
195	init_LFSR(&L,initial_state,taps);
196	encrypt("toy_pt.txt","ct.dat",&L);
197	init_LFSR(&L,initial_state,taps);
198	decrypt("ct.dat","toy_ot.txt",&L);
199    get_128_keystream_bits("target_ciphertext","THE PROJECT GUTEN");
200	shape_keystream();
201}