Open in CoCalc with one click!
1
/*
2
Code for 64 bit LFSR
3
Hunter Johnson
4
9/15/17
5
*/
6
7
#include <iostream>
8
#include <stdint.h>
9
#include <stdlib.h>
10
#include <stdio.h>
11
#include <assert.h>
12
13
using 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
23
typedef struct {
24
uint64_t state;
25
uint64_t taps;
26
} LFSR;
27
28
int 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
36
int read_lfsr(LFSR* L)
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
43
void 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
50
void 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
57
unsigned 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
{
66
//printf("%d\n",read_lfsr(L));
67
C |= (read_lfsr(L)<<i);
68
next_state(L);
69
}
70
//printf("\t%d\n",C);
71
return C;
72
}
73
74
void 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
94
void 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
102
void 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
131
void 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
190
int 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
}