1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
#include <stdio.h>
/* Masks for the three shift registers */
#define R1MASK 0x07FFFF /* 19 bits, numbered 0..18 */
#define R2MASK 0x3FFFFF /* 22 bits, numbered 0..21 */
#define R3MASK 0x7FFFFF /* 23 bits, numbered 0..22 */
/* Middle bit of each of the three shift registers, for clock control */
#define R1MID 0x000100 /* bit 8 */
#define R2MID 0x000400 /* bit 10 */
#define R3MID 0x000400 /* bit 10 */
/* Feedback taps, for clocking the shift registers.
* These correspond to the primitive polynomials
* x^19 + x^5 + x^2 + x + 1, x^22 + x + 1,
* and x^23 + x^15 + x^2 + x + 1. */
#define R1TAPS 0x072000 /* bits 18,17,16,13 */
#define R2TAPS 0x300000 /* bits 21,20 */
#define R3TAPS 0x700080 /* bits 22,21,20,7 */
/* Output taps, for output generation */
#define R1OUT 0x040000 /* bit 18 (the high bit) */
#define R2OUT 0x200000 /* bit 21 (the high bit) */
#define R3OUT 0x400000 /* bit 22 (the high bit) */
typedef unsigned char byte;
typedef unsigned long word;
typedef word bit;
/* Calculate the parity of a 32-bit word, i.e. the sum of its bits modulo 2 */
bit parity(word x) {
x ^= x>>16;
x ^= x>>8;
x ^= x>>4;
x ^= x>>2;
x ^= x>>1;
return x&1;
}
/* Clock one shift register */
word clockone(word reg, word mask, word taps) {
word t = reg & taps;
reg = (reg << 1) & mask;
reg |= parity(t);
return reg;
}
/* The three shift registers. They're in global variables to make the code
* easier to understand.
* A better implementation would not use global variables. */
word R1, R2, R3;
/* Look at the middle bits of R1,R2,R3, take a vote, and
* return the majority value of those 3 bits. */
bit majority() {
int sum;
sum = parity(R1&R1MID) + parity(R2&R2MID) + parity(R3&R3MID);
if (sum >= 2)
return 1;
else
return 0;
}
/* Clock two or three of R1,R2,R3, with clock control
* according to their middle bits.
* Specifically, we clock Ri whenever Ri's middle bit
* agrees with the majority value of the three middle bits.*/
void clock() {
bit maj = majority();
if (((R1&R1MID)!=0) == maj)
R1 = clockone(R1, R1MASK, R1TAPS);
if (((R2&R2MID)!=0) == maj)
R2 = clockone(R2, R2MASK, R2TAPS);
if (((R3&R3MID)!=0) == maj)
R3 = clockone(R3, R3MASK, R3TAPS);
}
/* Clock all three of R1,R2,R3, ignoring their middle bits.
* This is only used for key setup. */
void clockallthree() {
R1 = clockone(R1, R1MASK, R1TAPS);
R2 = clockone(R2, R2MASK, R2TAPS);
R3 = clockone(R3, R3MASK, R3TAPS);
}
/* Generate an output bit from the current state.
* You grab a bit from each register via the output generation taps;
* then you XOR the resulting three bits. */
bit getbit() {
return parity(R1&R1OUT)^parity(R2&R2OUT)^parity(R3&R3OUT);
}
/* Do the A5/1 key setup. This routine accepts a 64-bit key and
* a 22-bit frame number. */
void keysetup(byte key[8], word frame) {
int i;
bit keybit, framebit;
/* Zero out the shift registers. */
R1 = R2 = R3 = 0;
/* Load the key into the shift registers,
* LSB of first byte of key array first,
* clocking each register once for every
* key bit loaded. (The usual clock
* control rule is temporarily disabled.) */
for (i=0; i<64; i++) {
clockallthree(); /* always clock */
keybit = (key[i/8] >> (i&7)) & 1; /* The i-th bit of the
key */
R1 ^= keybit; R2 ^= keybit; R3 ^= keybit;
}
/* Load the frame number into the shift
* registers, LSB first,
* clocking each register once for every
* key bit loaded. (The usual clock
* control rule is still disabled.) */
for (i=0; i<22; i++) {
clockallthree(); /* always clock */
framebit = (frame >> i) & 1; /* The i-th bit of the frame #
*/
R1 ^= framebit; R2 ^= framebit; R3 ^= framebit;
}
/* Run the shift registers for 100 clocks
* to mix the keying material and frame number
* together with output generation disabled,
* so that there is sufficient avalanche.
* We re-enable the majority-based clock control
* rule from now on. */
for (i=0; i<100; i++) {
clock();
}
/* Now the key is properly set up. */
}
/* Generate output. We generate 228 bits of
* keystream output. The first 114 bits is for
* the A->B frame; the next 114 bits is for the
* B->A frame. You allocate a 15-byte buffer
* for each direction, and this function fills
* it in. */
void run(byte AtoBkeystream[], byte BtoAkeystream[]) {
int i;
/* Zero out the output buffers. */
for (i=0; i<=113/8; i++)
AtoBkeystream[i] = BtoAkeystream[i] = 0;
/* Generate 114 bits of keystream for the
* A->B direction. Store it, MSB first. */
for (i=0; i<114; i++) {
clock();
AtoBkeystream[i/8] |= getbit() << (7-(i&7));
}
/* Generate 114 bits of keystream for the
* B->A direction. Store it, MSB first. */
for (i=0; i<114; i++) {
clock();
BtoAkeystream[i/8] |= getbit() << (7-(i&7));
}
}
/* Test the code by comparing it against
* a known-good test vector. */
void test() {
byte key[8] = {0x12, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF};
word frame = 0x134;
byte goodAtoB[15] = { 0x53, 0x4E, 0xAA, 0x58, 0x2F, 0xE8, 0x15,
0x1A, 0xB6, 0xE1, 0x85, 0x5A, 0x72, 0x8C, 0x00 };
byte goodBtoA[15] = { 0x24, 0xFD, 0x35, 0xA3, 0x5D, 0x5F, 0xB6,
0x52, 0x6D, 0x32, 0xF9, 0x06, 0xDF, 0x1A, 0xC0 };
byte AtoB[15], BtoA[15];
int i, failed=0;
keysetup(key, frame);
run(AtoB, BtoA);
/* Compare against the test vector. */
for (i=0; i<15; i++)
if (AtoB[i] != goodAtoB[i])
failed = 1;
for (i=0; i<15; i++)
if (BtoA[i] != goodBtoA[i])
failed = 1;
/* Print some debugging output. */
printf("key: 0x");
for (i=0; i<8; i++)
printf("%02X", key[i]);
printf("\n");
printf("frame number: 0x%06X\n", (unsigned int)frame);
printf("known good output:\n");
printf(" A->B: 0x");
for (i=0; i<15; i++)
printf("%02X", goodAtoB[i]);
printf(" B->A: 0x");
for (i=0; i<15; i++)
printf("%02X", goodBtoA[i]);
printf("\n");
printf("observed output:\n");
printf(" A->B: 0x");
for (i=0; i<15; i++)
printf("%02X", AtoB[i]);
printf(" B->A: 0x");
for (i=0; i<15; i++)
printf("%02X", BtoA[i]);
printf("\n");
if (!failed) {
printf("Self-check succeeded: everything looks ok.\n");
return;
} else {
/* Problems! The test vectors didn't compare*/
printf("\nI don't know why this broke; contact the authors.\n");
exit(1);
}
}
int main(void) {
//Call Test now....
test();
getche();
return 0;
//Comment after return
}
| |
