Ticket #8764: des.sage

File des.sage, 16.4 KB (added by mvngu, 11 years ago)

original Sage script by Alasdair McAndrew?

Line 
1r"""
2DES
3
4An implementation of the Data Encryption Standard (DES).  This only  allows
5the encryption of a single 64-bit plaintext with a 64-bit key.
6
7It thus provides a foundation for the user to build up triple-DES,
8DES in standard NIST block modes (ECB, CBC etc), and for padding.  None
9of these are provided in this implementation.
10
11AUTHORS:
12
13- Alasdair McAndrew (2010-04): initial version
14"""
15
16###########################################################################
17# Copyright (c) 2009 Alasdair McAndrew <amca01@gmail.com>
18#
19# This program is free software; you can redistribute it and/or modify
20# it under the terms of the GNU General Public License as published by
21# the Free Software Foundation; either version 2 of the License, or
22# (at your option) any later version.
23#
24# This program is distributed in the hope that it will be useful,
25# but WITHOUT ANY WARRANTY; without even the implied warranty of
26# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
27# GNU General Public License for more details.
28#
29# http://www.gnu.org/licenses/
30###########################################################################
31
32# First some helper functions, not part pf the DES class, but useful
33
34def hex2bin(str): # turns a hexadecimal string into binary
35    tmp=str
36    if tmp[:2] != '0x':
37        tmp='0x'+tmp
38    if len(tmp) != 18:
39        raise ValueError("Invalid hexadecimal string size - must be 16")
40    tmp=bin(Integer(tmp))
41    if tmp[:2]=='0b':
42        tmp=tmp[2:]
43    return tmp.zfill(64)
44
45def bin2hex(str): # turns a binary string into hexadecimal
46    tmp=str
47    if tmp[:2] != '0b':
48        tmp='0b'+tmp
49    if len(tmp) != 66:
50        raise ValueError("Invalid binary string size - must be 64")
51    tmp=hex(Integer(tmp))
52    if tmp[:2]=='0x':
53        tmp=tmp[2:]
54    return tmp.zfill(16)
55
56def rivest_test(hexstr): # Applies Rivest's test for DES implementations
57        X=[hex2bin(hexstr) for i in range(17)]
58        for i in range(16):
59            di=DES(X[i])
60            if is_even(i):
61                X[i+1]=di.encrypt(X[i])
62            else:
63                X[i+1]=di.decrypt(X[i])
64        return bin2hex(X[16])
65
66from sage.monoids.string_monoid import BinaryStrings
67from sage.structure.sage_object import SageObject
68
69class DES(SageObject):
70    r"""
71    This class implements the Data Encryption Standard (DES) asw
72    described in NIST standard FIPS PUB 46-3 and available at
73    <http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf>
74
75    Input of both plaintext and key are 64 bit binary strings,
76    as is the output.  For ease of use, there are two "helper"
77    functions hex2bin and bin2hex which translate hexadecimal
78    to and from binary.
79
80    EXAMPLES:
81    sage: load DES.sage
82    sage: hexkey='0123456789abcdef'
83    sage: key=hex2bin(hexkey)
84    sage: D=DES(key)
85    sage: hexpl='aaaabbbbccccdddd'
86    sage: pl=hex2bin(hexpl)
87    sage: ct=D.encrypt(pl)
88    sage: bin2hex(ct)
89      '6f32c06fb6ac37bf'
90    sage: D.decrypt(ct)==pl
91      True
92
93    There is also a test developed by Ronald Rivest in
94    "TESTING IMPLEMENTATIONS OF DES" and available at
95    <http://people.csail.mit.edu/rivest/Destest.txt>:
96
97    sage: rivest_test('9474B8E8C73BCA7D')
98       '1b1a2ddb4c642438'
99
100    which is the correct value to obtain so that according to
101    the article: "your implementation does not have any of the
102    36,568 possible single-fault errors described herein."
103
104
105   
106    """
107
108    # Permutations and S-boxes
109
110    # PC1 obtains 56 bits from the original 64 bits of the key
111
112    __PC1 = [56, 48, 40, 32, 24, 16,  8,
113              0, 57, 49, 41, 33, 25, 17,
114              9,  1, 58, 50, 42, 34, 26,
115             18, 10,  2, 59, 51, 43, 35,
116             62, 54, 46, 38, 30, 22, 14,
117              6, 61, 53, 45, 37, 29, 21,
118             13,  5, 60, 52, 44, 36, 28,
119             20, 12,  4, 27, 19, 11,  3]
120
121     # PC2 is the compression permutation which reduces the key to 48 bits
122
123    __PC2 = [13, 16, 10, 23,  0,  4,
124              2, 27, 14,  5, 20,  9,
125             22, 18, 11,  3, 25,  7,
126             15,  6, 26, 19, 12,  1,
127             40, 51, 30, 36, 46, 54,
128             29, 39, 50, 44, 32, 47,
129             43, 48, 38, 55, 33, 52,
130             45, 41, 49, 35, 28, 31]
131
132    # initial permutation IP
133
134    __IP = [57, 49, 41, 33, 25, 17, 9,  1,
135            59, 51, 43, 35, 27, 19, 11, 3,
136            61, 53, 45, 37, 29, 21, 13, 5,
137            63, 55, 47, 39, 31, 23, 15, 7,
138            56, 48, 40, 32, 24, 16, 8,  0,
139            58, 50, 42, 34, 26, 18, 10, 2,
140            60, 52, 44, 36, 28, 20, 12, 4,
141            62, 54, 46, 38, 30, 22, 14, 6]
142
143     # Expansion table for turning 32 bit blocks into 48 bits
144
145    __E = [31,  0,  1,  2,  3,  4,
146            3,  4,  5,  6,  7,  8,
147            7,  8,  9, 10, 11, 12,
148           11, 12, 13, 14, 15, 16,
149           15, 16, 17, 18, 19, 20,
150           19, 20, 21, 22, 23, 24,
151           23, 24, 25, 26, 27, 28,
152           27, 28, 29, 30, 31,  0]
153
154    __sbox = [       # S1
155                [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
156                 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
157                 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
158                 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13],
159
160                # S2
161                [15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
162                 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
163                 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
164                 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9],
165
166                # S3
167                [10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
168                 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
169                 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
170                 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12],
171
172                # S4
173                [7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
174                 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
175                 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
176                 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14],
177
178                # S5
179                [2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
180                 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
181                 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
182                 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3],
183
184                # S6
185                [12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
186                 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
187                 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
188                 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13],
189
190                # S7
191                [4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
192                 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
193                 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
194                 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12],
195
196                # S8
197                [13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
198                 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
199                 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
200                 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11],
201        ]
202
203    # 32-bit permutation function P used on the output of the S-boxes
204    __P = [15,  6, 19, 20, 28, 11, 27, 16,
205            0, 14, 22, 25,  4, 17, 30,  9,
206            1,  7, 23, 13, 31, 26,  2,  8,
207           18, 12, 29,  5, 21, 10,  3, 24]
208
209    # final permutation IP^-1
210    __FP = [39,  7, 47, 15, 55, 23, 63, 31,
211            38,  6, 46, 14, 54, 22, 62, 30,
212            37,  5, 45, 13, 53, 21, 61, 29,
213            36,  4, 44, 12, 52, 20, 60, 28,
214            35,  3, 43, 11, 51, 19, 59, 27,
215            34,  2, 42, 10, 50, 18, 58, 26,
216            33,  1, 41,  9, 49, 17, 57, 25,
217            32,  0, 40,  8, 48, 16, 56, 24]
218
219    def __init__(self,key):
220        # Sanity checking of arguments.
221        if set(map(Integer,key)) != set([0,1]):
222            raise ValueError("Invalid key - must be binary")
223        if len(key) != 64:
224            raise ValueError("Invalid DES key size. Key must be exactly 64 bits long.")
225        self.__key=key
226
227    def _repr_(self):
228        return "DES cryptosystem with 64 bit plaintext and key"
229 
230    def __keyschedule(self): # Obtains all subkeys from an initial 64 bit key k
231        tmp=join([self.__key[i] for i in self.__PC1],'') # Permute the key bits according to PC1
232        ks=[]
233        shifts=[1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]
234        for i in shifts:   
235            c=tmp[:28]
236            d=tmp[28:]
237            cs=c[i:]+c[:i]
238            ds=d[i:]+d[:i]
239            tmp=cs+ds
240            h=join([tmp[i] for i in self.__PC2],'')
241            ks.append(h)
242            # print hex(Integer('0b'+h)).zfill(12)
243        return ks
244
245    def __xor(self,str1,str2): # returns the string made by bit-wise xor of the bits of str1 and str2
246        return join([str(Integer(x)^^Integer(y)) for (x,y) in zip(str1,str2)],'')
247
248    def __apply_sbox(self,str,n): # Applies sbox n to six bit string str
249        s=map(Integer,str)
250        row=2*s[0]+s[5]
251        col=8*s[1]+4*s[2]+2*s[3]+s[4]
252        return bin(self.__sbox[n][16*row+col])[2:].zfill(4)
253
254    def __f(self,R0,keys,m):
255            # This is the function which mixes the 32 bit right half with subkey m
256        R1=join([R0[i] for i in self.__E],'')  # First expand to 48 bits
257        R2=self.__xor(R1,keys[m])              # Then add the current subkey
258        R3=join([self.__apply_sbox(R2[6*i:6*i+6],i) for i in range(8)],'') 
259                                       # Apply the sboxes to each six bits
260        R4=join([R3[i] for i in self.__P],'')  # Then reduce to 32 bits
261        return R4
262
263    def encrypt(self, plaintext): # DES encryption
264        r"""
265        Encrypts a single plaintext with the instance of DES.
266
267        EXAMPLES:
268        sage: k1=8*'01010011'
269        sage: k2=8*'10011001'
270        sage: D1=DES(k1)
271        sage: D2=DES(k2)
272        sage: pl=64*'0'
273        sage: ct1=D1.encrypt(pl)
274        sage: bin2hex(ct1)
275          '17d819b45d919a56'
276        sage: ct2=D2.encrypt(pl)
277        sage: bin2hex(ct2)
278          '0f2fcf4aeb6c56d4'
279
280        """
281        # Sanity checking of arguments.
282        if len(plaintext) != 64:
283            raise ValueError("Invalid DES plaintext size. Plaintext must be exactly 64 bits long.")
284        pl=join([plaintext[i] for i in self.__IP],'')
285            # first permute the bits of the plaintext
286        ks=self.__keyschedule() # Create all the subkeys
287        L=pl[:32] # Obtain left and right halves
288        R=pl[32:]
289        for i in range(16):
290            tmp=R
291            R=self.__xor(self.__f(tmp,ks,i),L)
292            L=tmp
293    #       print "i,L+R=",i,hex(Integer('0b'+L)).zfill(8),hex(Integer('0b'+R)).zfill(8)
294        out=R+L
295        return join([out[i] for i in self.__FP],'')
296
297    def decrypt(self,ciphertext): # DES decryption
298        r"""
299        Decrypts a single ciphertext with the instance of DES.
300
301        EXAMPLES:
302        sage: k1=8*'01010011'
303        sage: k2=8*'10011001'
304        sage: D1=DES(k1)
305        sage: D2=DES(k2)
306        sage: pl=64*'0'
307        sage: ct1=D1.encrypt(pl)
308        sage: bin2hex(ct1)
309          '17d819b45d919a56'
310        sage: ct2=D2.encrypt(pl)
311        sage: bin2hex(ct2)
312          '0f2fcf4aeb6c56d4'
313        sage: de1=D1.decrypt(ct1)
314        sage: bin2hex(de1)
315          '0000000000000000'
316        sage: de2=D2.decrypt(ct2)
317        sage: bin2hex(de2)
318          '0000000000000000'
319 
320
321        """
322        # Sanity checking of arguments.
323        if len(ciphertext) != 64:
324            raise ValueError("Invalid DES ciphertext size. Ciphertext must be exactly 64 bits long.")
325        ct=join([ciphertext[i] for i in self.__IP],'') # first permute the bits of the ciphertext
326        ks=self.__keyschedule() # Create all the subkeys
327        L=ct[:32] # Obtain left and right halves
328        R=ct[32:]
329        for i in range(16):
330            tmp=R
331            R=self.__xor(self.__f(tmp,ks,15-i),L)
332                # Apply subkeys in opposite order from encryption
333            L=tmp
334            # print "i,L+R=",i,hex(Integer('0b'+L)).zfill(8),hex(Integer('0b'+R)).zfill(8)
335        out=R+L
336        return join([out[i] for i in self.__FP],'')
337
338    def getkey(self): # Returns the key used
339        r"""
340        Returns the current key.
341
342        EXAMPLES:
343        sage: k1=8*'01010011'
344        sage: D1=DES(k1)
345        sage: D1.getkey()
346          '0101001101010011010100110101001101010011010100110101001101010011'
347        sage: bin2hex(_)
348          '5353535353535353'
349
350        """
351
352        return self.__key
353
354    def setkey(self,newkey): # Changes the key for this instance of DES
355        r"""
356        Changes the key for this instance of DES.
357
358        EXAMPLES:
359        sage: k1=8*'01010011'
360        sage: D1=DES(k1)
361        sage: D1.setkey(8*'10011001')
362        sage: bin2hex(D1.getkey())
363          '9999999999999999'
364
365        """
366        self.__key=newkey
367   
368    def avalanche(self,plaintext1,plaintext2):
369        r"""
370        Demontrates the avalanche effect for two different plaintexts.
371        Given two plaintexts pl1 and pl2, then the call for an instance
372        D1 of DES:
373
374        sage: D1.avalanche(pl1,pl2)
375
376        will print 16 rows of  values, one for each round of DES.  Each row
377        contains the round number, the number of differences between the
378        current value for each plaintext, and a string representing the
379        bit-wise exclusive-ors between the two strings.  So the number
380        of differences is just the number of ones in the exclusive-or string.
381
382        The avalanche effect is best shown when the two plaintexts differ
383        at a single position.
384
385        EXAMPLES:
386        sage: k1=8*'01010011'
387        sage: D1=DES(k1)
388        sage: pl1=8*'10011100'
389        sage: pl2=7*'10011100"="1011101'
390        sage: D1.avalanche(pl1,pl2)
391        1 1 0000000000000000000000000000000000000000000000000000000010000000
392        2 7 0000000000000000000000001000000000010000001100000000010000001001
393        3 25 0001000000110000000001000000100100010110111110100011010011111110
394        4 31 0001011011111010001101001111111001010001100000010111100000010011
395        5 30 0101000110000001011110000001001110110101101000001101110111010101
396        6 32 1011010110100000110111011101010101000001110010110100000110110011
397        7 34 0100000111001011010000011011001111011111000010011011111100111100
398        8 37 1101111100001001101111110011110000111000010101011110101100101110
399        9 35 0011100001010101111010110010111001011000001101110100010110111111
400        10 33 0101100000110111010001011011111101101101000100000100001011111110
401        11 37 0110110100010000010000101111111011101111110011110111000110011101
402        12 38 1110111111001111011100011001110110100011010010110110000000111111
403        13 35 1010001101001011011000000011111110100001110011010011011111011101
404        14 30 1010000111001101001101111101110110000000010101001001101000110001
405        15 25 1000000001010100100110100011000100100110111010101000000010111010
406        16 30 0010011011101010100000001011101010001101001110010000100111101011
407 
408        ['1011110101110101010100111011111101011100110110011010101001011100',
409         '1110100011010110100100111100100001001110011010101000101100110111']
410
411        This shows that after the first few rounds half of the bits have changed.
412
413       
414 
415
416        """
417        # Checks the avalanche criterion for two different plaintexts
418        pl1=join([plaintext1[i] for i in self.__IP],'')
419            # first permute the bits of the plaintext
420        pl2=join([plaintext2[i] for i in self.__IP],'')
421            # first permute the bits of the plaintext
422        ks=self.__keyschedule() # Create all the subkeys
423        L1=pl1[:32] # Obtain left and right halves
424        R1=pl1[32:]
425        L2=pl2[:32] # Obtain left and right halves
426        R2=pl2[32:]
427        for i in range(16):
428            tmp1=R1
429            tmp2=R2
430            R1=self.__xor(self.__f(tmp1,ks,i),L1)
431            R2=self.__xor(self.__f(tmp2,ks,i),L2)
432            L1=tmp1
433            L2=tmp2
434            X=self.__xor(L1+R1,L2+R2)
435            wt=sum(Integer(i) for i in X)
436            print i+1,wt,X
437        out1=R1+L1
438        out2=R2+L2
439        return [join([out1[i] for i in self.__FP],''),join([out2[i] for i in self.__FP],'')]
440
441# Avalanche with two separate keys - not yet properly implemented
442
443    def avalanche_k(plaintext,key1,key2):
444        pl=join([plaintext[i] for i in IP],'') # first permute the bits of the plaintext
445        ks1=keyschedule(key1) # Create all the subkeys
446        ks2=keyschedule(key2) # Create all the subkeys
447        L1=pl[:32] # Obtain left and right halves
448        R1=pl[32:]
449        L2=pl[:32] 
450        R2=pl[32:]
451        for i in range(16):
452            tmp1=R1
453            tmp2=R2
454            R1=xor(f(tmp1,ks1,i),L1)
455            R2=xor(f(tmp2,ks2,i),L2)
456            L1=tmp1
457            L2=tmp2
458            X=xor(L1+R1,L2+R2)
459            wt=sum(Integer(i) for i in X)
460            print i+1,wt,X
461        out1=R1+L1
462        out2=R2+L2
463        return [join([out1[i] for i in FP],''),join([out2[i] for i in FP],'')]