-
Notifications
You must be signed in to change notification settings - Fork 1
/
rijndael.py
171 lines (158 loc) · 43.6 KB
/
rijndael.py
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
#"""
#A pure python (slow) implementation of rijndael with a decent interface
#
#To include -
#
#from rijndael import rijndael
#
#To do a key setup -
#
#r = rijndael(key, block_size = 16)
#
#key must be a string of length 16, 24, or 32
#blocksize must be 16, 24, or 32. Default is 16
#
#To use -
#
#ciphertext = r.encrypt(plaintext)
#plaintext = r.decrypt(ciphertext)
#
#If any strings are of the wrong length a ValueError is thrown
#"""
# ported from the Java reference code by Bram Cohen, April 2001
# this code is public domain, unless someone makes
# an intellectual property claim against the reference
# code, in which case it can be made public domain by
# deleting all the comments and renaming all the variables
__version__ = "1.3.0" #version of this file
__all__ = ["rijndael"]
shifts = (((0, 0), (1, 3), (2, 2), (3, 1)),
((0, 0), (1, 5), (2, 4), (3, 3)),
((0, 0), (1, 7), (3, 5), (4, 4)))
# [keysize][block_size]
num_rounds = {16: {16: 10, 24: 12, 32: 14}, 24: {16: 12, 24: 12, 32: 14}, 32: {16: 14, 24: 14, 32: 14}}
#precalculated tables
rcon = (1, 2, 4, 8, 16, 32, 64, 128, 27, 54, 108, 216, 171, 77, 154, 47, 94, 188, 99, 198, 151, 53, 106, 212, 179, 125, 250, 239, 197, 145)
S = (99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22)
T1 = (3328402341L, 4168907908L, 4000806809L, 4135287693L, 4294111757L, 3597364157L, 3731845041L, 2445657428L, 1613770832, 33620227, 3462883241L, 1445669757, 3892248089L, 3050821474L, 1303096294, 3967186586L, 2412431941L, 528646813, 2311702848L, 4202528135L, 4026202645L, 2992200171L, 2387036105L, 4226871307L, 1101901292, 3017069671L, 1604494077, 1169141738, 597466303, 1403299063, 3832705686L, 2613100635L, 1974974402, 3791519004L, 1033081774, 1277568618, 1815492186, 2118074177, 4126668546L, 2211236943L, 1748251740, 1369810420, 3521504564L, 4193382664L, 3799085459L, 2883115123L, 1647391059, 706024767, 134480908, 2512897874L, 1176707941, 2646852446L, 806885416, 932615841, 168101135, 798661301, 235341577, 605164086, 461406363, 3756188221L, 3454790438L, 1311188841, 2142417613, 3933566367L, 302582043, 495158174, 1479289972, 874125870, 907746093, 3698224818L, 3025820398L, 1537253627, 2756858614L, 1983593293, 3084310113L, 2108928974, 1378429307, 3722699582L, 1580150641, 327451799, 2790478837L, 3117535592L, 0, 3253595436L, 1075847264, 3825007647L, 2041688520, 3059440621L, 3563743934L, 2378943302L, 1740553945, 1916352843, 2487896798L, 2555137236L, 2958579944L, 2244988746L, 3151024235L, 3320835882L, 1336584933, 3992714006L, 2252555205L, 2588757463L, 1714631509, 293963156, 2319795663L, 3925473552L, 67240454, 4269768577L, 2689618160L, 2017213508, 631218106, 1269344483, 2723238387L, 1571005438, 2151694528L, 93294474, 1066570413, 563977660, 1882732616, 4059428100L, 1673313503, 2008463041, 2950355573L, 1109467491, 537923632, 3858759450L, 4260623118L, 3218264685L, 2177748300L, 403442708, 638784309, 3287084079L, 3193921505L, 899127202, 2286175436L, 773265209, 2479146071L, 1437050866, 4236148354L, 2050833735, 3362022572L, 3126681063L, 840505643, 3866325909L, 3227541664L, 427917720, 2655997905L, 2749160575L, 1143087718, 1412049534, 999329963, 193497219, 2353415882L, 3354324521L, 1807268051, 672404540, 2816401017L, 3160301282L, 369822493, 2916866934L, 3688947771L, 1681011286, 1949973070, 336202270, 2454276571L, 201721354, 1210328172, 3093060836L, 2680341085L, 3184776046L, 1135389935, 3294782118L, 965841320, 831886756, 3554993207L, 4068047243L, 3588745010L, 2345191491L, 1849112409, 3664604599L, 26054028, 2983581028L, 2622377682L, 1235855840, 3630984372L, 2891339514L, 4092916743L, 3488279077L, 3395642799L, 4101667470L, 1202630377, 268961816, 1874508501, 4034427016L, 1243948399, 1546530418, 941366308, 1470539505, 1941222599, 2546386513L, 3421038627L, 2715671932L, 3899946140L, 1042226977, 2521517021L, 1639824860, 227249030, 260737669, 3765465232L, 2084453954, 1907733956, 3429263018L, 2420656344L, 100860677, 4160157185L, 470683154, 3261161891L, 1781871967, 2924959737L, 1773779408, 394692241, 2579611992L, 974986535, 664706745, 3655459128L, 3958962195L, 731420851, 571543859, 3530123707L, 2849626480L, 126783113, 865375399, 765172662, 1008606754, 361203602, 3387549984L, 2278477385L, 2857719295L, 1344809080, 2782912378L, 59542671, 1503764984, 160008576, 437062935, 1707065306, 3622233649L, 2218934982L, 3496503480L, 2185314755L, 697932208, 1512910199, 504303377, 2075177163, 2824099068L, 1841019862, 739644986)
T2 = (2781242211L, 2230877308L, 2582542199L, 2381740923L, 234877682, 3184946027L, 2984144751L, 1418839493, 1348481072, 50462977, 2848876391L, 2102799147, 434634494, 1656084439, 3863849899L, 2599188086L, 1167051466, 2636087938L, 1082771913, 2281340285L, 368048890, 3954334041L, 3381544775L, 201060592, 3963727277L, 1739838676, 4250903202L, 3930435503L, 3206782108L, 4149453988L, 2531553906L, 1536934080, 3262494647L, 484572669, 2923271059L, 1783375398, 1517041206, 1098792767, 49674231, 1334037708, 1550332980, 4098991525L, 886171109, 150598129, 2481090929L, 1940642008, 1398944049, 1059722517, 201851908, 1385547719, 1699095331, 1587397571, 674240536, 2704774806L, 252314885, 3039795866L, 151914247, 908333586, 2602270848L, 1038082786, 651029483, 1766729511, 3447698098L, 2682942837L, 454166793, 2652734339L, 1951935532, 775166490, 758520603, 3000790638L, 4004797018L, 4217086112L, 4137964114L, 1299594043, 1639438038, 3464344499L, 2068982057, 1054729187, 1901997871, 2534638724L, 4121318227L, 1757008337, 0, 750906861, 1614815264, 535035132, 3363418545L, 3988151131L, 3201591914L, 1183697867, 3647454910L, 1265776953, 3734260298L, 3566750796L, 3903871064L, 1250283471, 1807470800, 717615087, 3847203498L, 384695291, 3313910595L, 3617213773L, 1432761139, 2484176261L, 3481945413L, 283769337, 100925954, 2180939647L, 4037038160L, 1148730428, 3123027871L, 3813386408L, 4087501137L, 4267549603L, 3229630528L, 2315620239L, 2906624658L, 3156319645L, 1215313976, 82966005, 3747855548L, 3245848246L, 1974459098, 1665278241, 807407632, 451280895, 251524083, 1841287890, 1283575245, 337120268, 891687699, 801369324, 3787349855L, 2721421207L, 3431482436L, 959321879, 1469301956, 4065699751L, 2197585534L, 1199193405, 2898814052L, 3887750493L, 724703513, 2514908019L, 2696962144L, 2551808385L, 3516813135L, 2141445340, 1715741218, 2119445034, 2872807568L, 2198571144L, 3398190662L, 700968686, 3547052216L, 1009259540, 2041044702, 3803995742L, 487983883, 1991105499, 1004265696, 1449407026, 1316239930, 504629770, 3683797321L, 168560134, 1816667172, 3837287516L, 1570751170, 1857934291, 4014189740L, 2797888098L, 2822345105L, 2754712981L, 936633572, 2347923833L, 852879335, 1133234376, 1500395319, 3084545389L, 2348912013L, 1689376213, 3533459022L, 3762923945L, 3034082412L, 4205598294L, 133428468, 634383082, 2949277029L, 2398386810L, 3913789102L, 403703816, 3580869306L, 2297460856L, 1867130149, 1918643758, 607656988, 4049053350L, 3346248884L, 1368901318, 600565992, 2090982877, 2632479860L, 557719327, 3717614411L, 3697393085L, 2249034635L, 2232388234L, 2430627952L, 1115438654, 3295786421L, 2865522278L, 3633334344L, 84280067, 33027830, 303828494, 2747425121L, 1600795957, 4188952407L, 3496589753L, 2434238086L, 1486471617, 658119965, 3106381470L, 953803233, 334231800, 3005978776L, 857870609, 3151128937L, 1890179545, 2298973838L, 2805175444L, 3056442267L, 574365214, 2450884487L, 550103529, 1233637070, 4289353045L, 2018519080, 2057691103, 2399374476L, 4166623649L, 2148108681L, 387583245, 3664101311L, 836232934, 3330556482L, 3100665960L, 3280093505L, 2955516313L, 2002398509, 287182607, 3413881008L, 4238890068L, 3597515707L, 975967766)
T3 = (1671808611, 2089089148, 2006576759, 2072901243, 4061003762L, 1807603307, 1873927791, 3310653893L, 810573872, 16974337, 1739181671, 729634347, 4263110654L, 3613570519L, 2883997099L, 1989864566, 3393556426L, 2191335298L, 3376449993L, 2106063485, 4195741690L, 1508618841, 1204391495, 4027317232L, 2917941677L, 3563566036L, 2734514082L, 2951366063L, 2629772188L, 2767672228L, 1922491506, 3227229120L, 3082974647L, 4246528509L, 2477669779L, 644500518, 911895606, 1061256767, 4144166391L, 3427763148L, 878471220, 2784252325L, 3845444069L, 4043897329L, 1905517169, 3631459288L, 827548209, 356461077, 67897348, 3344078279L, 593839651, 3277757891L, 405286936, 2527147926L, 84871685, 2595565466L, 118033927, 305538066, 2157648768L, 3795705826L, 3945188843L, 661212711, 2999812018L, 1973414517, 152769033, 2208177539L, 745822252, 439235610, 455947803, 1857215598, 1525593178, 2700827552L, 1391895634, 994932283, 3596728278L, 3016654259L, 695947817, 3812548067L, 795958831, 2224493444L, 1408607827, 3513301457L, 0, 3979133421L, 543178784, 4229948412L, 2982705585L, 1542305371, 1790891114, 3410398667L, 3201918910L, 961245753, 1256100938, 1289001036, 1491644504, 3477767631L, 3496721360L, 4012557807L, 2867154858L, 4212583931L, 1137018435, 1305975373, 861234739, 2241073541L, 1171229253, 4178635257L, 33948674, 2139225727, 1357946960, 1011120188, 2679776671L, 2833468328L, 1374921297, 2751356323L, 1086357568, 2408187279L, 2460827538L, 2646352285L, 944271416, 4110742005L, 3168756668L, 3066132406L, 3665145818L, 560153121, 271589392, 4279952895L, 4077846003L, 3530407890L, 3444343245L, 202643468, 322250259, 3962553324L, 1608629855, 2543990167L, 1154254916, 389623319, 3294073796L, 2817676711L, 2122513534, 1028094525, 1689045092, 1575467613, 422261273, 1939203699, 1621147744, 2174228865L, 1339137615, 3699352540L, 577127458, 712922154, 2427141008L, 2290289544L, 1187679302, 3995715566L, 3100863416L, 339486740, 3732514782L, 1591917662, 186455563, 3681988059L, 3762019296L, 844522546, 978220090, 169743370, 1239126601, 101321734, 611076132, 1558493276, 3260915650L, 3547250131L, 2901361580L, 1655096418, 2443721105L, 2510565781L, 3828863972L, 2039214713, 3878868455L, 3359869896L, 928607799, 1840765549, 2374762893L, 3580146133L, 1322425422, 2850048425L, 1823791212, 1459268694, 4094161908L, 3928346602L, 1706019429, 2056189050, 2934523822L, 135794696, 3134549946L, 2022240376, 628050469, 779246638, 472135708, 2800834470L, 3032970164L, 3327236038L, 3894660072L, 3715932637L, 1956440180, 522272287, 1272813131, 3185336765L, 2340818315L, 2323976074L, 1888542832, 1044544574, 3049550261L, 1722469478, 1222152264, 50660867, 4127324150L, 236067854, 1638122081, 895445557, 1475980887, 3117443513L, 2257655686L, 3243809217L, 489110045, 2662934430L, 3778599393L, 4162055160L, 2561878936L, 288563729, 1773916777, 3648039385L, 2391345038L, 2493985684L, 2612407707L, 505560094, 2274497927L, 3911240169L, 3460925390L, 1442818645, 678973480, 3749357023L, 2358182796L, 2717407649L, 2306869641L, 219617805, 3218761151L, 3862026214L, 1120306242, 1756942440, 1103331905, 2578459033L, 762796589, 252780047, 2966125488L, 1425844308, 3151392187L, 372911126)
T4 = (1667474886, 2088535288, 2004326894, 2071694838, 4075949567L, 1802223062, 1869591006, 3318043793L, 808472672, 16843522, 1734846926, 724270422, 4278065639L, 3621216949L, 2880169549L, 1987484396, 3402253711L, 2189597983L, 3385409673L, 2105378810, 4210693615L, 1499065266, 1195886990, 4042263547L, 2913856577L, 3570689971L, 2728590687L, 2947541573L, 2627518243L, 2762274643L, 1920112356, 3233831835L, 3082273397L, 4261223649L, 2475929149L, 640051788, 909531756, 1061110142, 4160160501L, 3435941763L, 875846760, 2779116625L, 3857003729L, 4059105529L, 1903268834, 3638064043L, 825316194, 353713962, 67374088, 3351728789L, 589522246, 3284360861L, 404236336, 2526454071L, 84217610, 2593830191L, 117901582, 303183396, 2155911963L, 3806477791L, 3958056653L, 656894286, 2998062463L, 1970642922, 151591698, 2206440989L, 741110872, 437923380, 454765878, 1852748508, 1515908788, 2694904667L, 1381168804, 993742198, 3604373943L, 3014905469L, 690584402, 3823320797L, 791638366, 2223281939L, 1398011302, 3520161977L, 0, 3991743681L, 538992704, 4244381667L, 2981218425L, 1532751286, 1785380564, 3419096717L, 3200178535L, 960056178, 1246420628, 1280103576, 1482221744, 3486468741L, 3503319995L, 4025428677L, 2863326543L, 4227536621L, 1128514950, 1296947098, 859002214, 2240123921L, 1162203018, 4193849577L, 33687044, 2139062782, 1347481760, 1010582648, 2678045221L, 2829640523L, 1364325282, 2745433693L, 1077985408, 2408548869L, 2459086143L, 2644360225L, 943212656, 4126475505L, 3166494563L, 3065430391L, 3671750063L, 555836226, 269496352, 4294908645L, 4092792573L, 3537006015L, 3452783745L, 202118168, 320025894, 3974901699L, 1600119230, 2543297077L, 1145359496, 387397934, 3301201811L, 2812801621L, 2122220284, 1027426170, 1684319432, 1566435258, 421079858, 1936954854, 1616945344, 2172753945L, 1330631070, 3705438115L, 572679748, 707427924, 2425400123L, 2290647819L, 1179044492, 4008585671L, 3099120491L, 336870440, 3739122087L, 1583276732, 185277718, 3688593069L, 3772791771L, 842159716, 976899700, 168435220, 1229577106, 101059084, 606366792, 1549591736, 3267517855L, 3553849021L, 2897014595L, 1650632388, 2442242105L, 2509612081L, 3840161747L, 2038008818, 3890688725L, 3368567691L, 926374254, 1835907034, 2374863873L, 3587531953L, 1313788572, 2846482505L, 1819063512, 1448540844, 4109633523L, 3941213647L, 1701162954, 2054852340, 2930698567L, 134748176, 3132806511L, 2021165296, 623210314, 774795868, 471606328, 2795958615L, 3031746419L, 3334885783L, 3907527627L, 3722280097L, 1953799400, 522133822, 1263263126, 3183336545L, 2341176845L, 2324333839L, 1886425312, 1044267644, 3048588401L, 1718004428, 1212733584, 50529542, 4143317495L, 235803164, 1633788866, 892690282, 1465383342, 3115962473L, 2256965911L, 3250673817L, 488449850, 2661202215L, 3789633753L, 4177007595L, 2560144171L, 286339874, 1768537042, 3654906025L, 2391705863L, 2492770099L, 2610673197L, 505291324, 2273808917L, 3924369609L, 3469625735L, 1431699370, 673740880, 3755965093L, 2358021891L, 2711746649L, 2307489801L, 218961690, 3217021541L, 3873845719L, 1111672452, 1751693520, 1094828930, 2576986153L, 757954394, 252645662, 2964376443L, 1414855848, 3149649517L, 370555436)
T5 = (1374988112, 2118214995, 437757123, 975658646, 1001089995, 530400753, 2902087851L, 1273168787, 540080725, 2910219766L, 2295101073L, 4110568485L, 1340463100, 3307916247L, 641025152, 3043140495L, 3736164937L, 632953703, 1172967064, 1576976609, 3274667266L, 2169303058L, 2370213795L, 1809054150, 59727847, 361929877, 3211623147L, 2505202138L, 3569255213L, 1484005843, 1239443753, 2395588676L, 1975683434, 4102977912L, 2572697195L, 666464733, 3202437046L, 4035489047L, 3374361702L, 2110667444, 1675577880, 3843699074L, 2538681184L, 1649639237, 2976151520L, 3144396420L, 4269907996L, 4178062228L, 1883793496, 2403728665L, 2497604743L, 1383856311, 2876494627L, 1917518562, 3810496343L, 1716890410, 3001755655L, 800440835, 2261089178L, 3543599269L, 807962610, 599762354, 33778362, 3977675356L, 2328828971L, 2809771154L, 4077384432L, 1315562145, 1708848333, 101039829, 3509871135L, 3299278474L, 875451293, 2733856160L, 92987698, 2767645557L, 193195065, 1080094634, 1584504582, 3178106961L, 1042385657, 2531067453L, 3711829422L, 1306967366, 2438237621L, 1908694277, 67556463, 1615861247, 429456164, 3602770327L, 2302690252L, 1742315127, 2968011453L, 126454664, 3877198648L, 2043211483, 2709260871L, 2084704233, 4169408201L, 0, 159417987, 841739592, 504459436, 1817866830, 4245618683L, 260388950, 1034867998, 908933415, 168810852, 1750902305, 2606453969L, 607530554, 202008497, 2472011535L, 3035535058L, 463180190, 2160117071L, 1641816226, 1517767529, 470948374, 3801332234L, 3231722213L, 1008918595, 303765277, 235474187, 4069246893L, 766945465, 337553864, 1475418501, 2943682380L, 4003061179L, 2743034109L, 4144047775L, 1551037884, 1147550661, 1543208500, 2336434550L, 3408119516L, 3069049960L, 3102011747L, 3610369226L, 1113818384, 328671808, 2227573024L, 2236228733L, 3535486456L, 2935566865L, 3341394285L, 496906059, 3702665459L, 226906860, 2009195472, 733156972, 2842737049L, 294930682, 1206477858, 2835123396L, 2700099354L, 1451044056, 573804783, 2269728455L, 3644379585L, 2362090238L, 2564033334L, 2801107407L, 2776292904L, 3669462566L, 1068351396, 742039012, 1350078989, 1784663195, 1417561698, 4136440770L, 2430122216L, 775550814, 2193862645L, 2673705150L, 1775276924, 1876241833, 3475313331L, 3366754619L, 270040487, 3902563182L, 3678124923L, 3441850377L, 1851332852, 3969562369L, 2203032232L, 3868552805L, 2868897406L, 566021896, 4011190502L, 3135740889L, 1248802510, 3936291284L, 699432150, 832877231, 708780849, 3332740144L, 899835584, 1951317047, 4236429990L, 3767586992L, 866637845, 4043610186L, 1106041591, 2144161806, 395441711, 1984812685, 1139781709, 3433712980L, 3835036895L, 2664543715L, 1282050075, 3240894392L, 1181045119, 2640243204L, 25965917, 4203181171L, 4211818798L, 3009879386L, 2463879762L, 3910161971L, 1842759443, 2597806476L, 933301370, 1509430414, 3943906441L, 3467192302L, 3076639029L, 3776767469L, 2051518780, 2631065433L, 1441952575, 404016761, 1942435775, 1408749034, 1610459739, 3745345300L, 2017778566, 3400528769L, 3110650942L, 941896748, 3265478751L, 371049330, 3168937228L, 675039627, 4279080257L, 967311729, 135050206, 3635733660L, 1683407248, 2076935265, 3576870512L, 1215061108, 3501741890L)
T6 = (1347548327, 1400783205, 3273267108L, 2520393566L, 3409685355L, 4045380933L, 2880240216L, 2471224067L, 1428173050, 4138563181L, 2441661558L, 636813900, 4233094615L, 3620022987L, 2149987652L, 2411029155L, 1239331162, 1730525723, 2554718734L, 3781033664L, 46346101, 310463728, 2743944855L, 3328955385L, 3875770207L, 2501218972L, 3955191162L, 3667219033L, 768917123, 3545789473L, 692707433, 1150208456, 1786102409, 2029293177, 1805211710, 3710368113L, 3065962831L, 401639597, 1724457132, 3028143674L, 409198410, 2196052529L, 1620529459, 1164071807, 3769721975L, 2226875310L, 486441376, 2499348523L, 1483753576, 428819965, 2274680428L, 3075636216L, 598438867, 3799141122L, 1474502543, 711349675, 129166120, 53458370, 2592523643L, 2782082824L, 4063242375L, 2988687269L, 3120694122L, 1559041666, 730517276, 2460449204L, 4042459122L, 2706270690L, 3446004468L, 3573941694L, 533804130, 2328143614L, 2637442643L, 2695033685L, 839224033, 1973745387, 957055980, 2856345839L, 106852767, 1371368976, 4181598602L, 1033297158, 2933734917L, 1179510461, 3046200461L, 91341917, 1862534868, 4284502037L, 605657339, 2547432937L, 3431546947L, 2003294622, 3182487618L, 2282195339L, 954669403, 3682191598L, 1201765386, 3917234703L, 3388507166L, 0, 2198438022L, 1211247597, 2887651696L, 1315723890, 4227665663L, 1443857720, 507358933, 657861945, 1678381017, 560487590, 3516619604L, 975451694, 2970356327L, 261314535, 3535072918L, 2652609425L, 1333838021, 2724322336L, 1767536459, 370938394, 182621114, 3854606378L, 1128014560, 487725847, 185469197, 2918353863L, 3106780840L, 3356761769L, 2237133081L, 1286567175, 3152976349L, 4255350624L, 2683765030L, 3160175349L, 3309594171L, 878443390, 1988838185, 3704300486L, 1756818940, 1673061617, 3403100636L, 272786309, 1075025698, 545572369, 2105887268, 4174560061L, 296679730, 1841768865, 1260232239, 4091327024L, 3960309330L, 3497509347L, 1814803222, 2578018489L, 4195456072L, 575138148, 3299409036L, 446754879, 3629546796L, 4011996048L, 3347532110L, 3252238545L, 4270639778L, 915985419, 3483825537L, 681933534, 651868046, 2755636671L, 3828103837L, 223377554, 2607439820L, 1649704518, 3270937875L, 3901806776L, 1580087799, 4118987695L, 3198115200L, 2087309459, 2842678573L, 3016697106L, 1003007129, 2802849917L, 1860738147, 2077965243, 164439672, 4100872472L, 32283319, 2827177882L, 1709610350, 2125135846, 136428751, 3874428392L, 3652904859L, 3460984630L, 3572145929L, 3593056380L, 2939266226L, 824852259, 818324884, 3224740454L, 930369212, 2801566410L, 2967507152L, 355706840, 1257309336, 4148292826L, 243256656, 790073846, 2373340630L, 1296297904, 1422699085, 3756299780L, 3818836405L, 457992840, 3099667487L, 2135319889, 77422314, 1560382517, 1945798516, 788204353, 1521706781, 1385356242, 870912086, 325965383, 2358957921L, 2050466060, 2388260884L, 2313884476L, 4006521127L, 901210569, 3990953189L, 1014646705, 1503449823, 1062597235, 2031621326, 3212035895L, 3931371469L, 1533017514, 350174575, 2256028891L, 2177544179L, 1052338372, 741876788, 1606591296, 1914052035, 213705253, 2334669897L, 1107234197, 1899603969, 3725069491L, 2631447780L, 2422494913L, 1635502980, 1893020342, 1950903388, 1120974935)
T7 = (2807058932L, 1699970625, 2764249623L, 1586903591, 1808481195, 1173430173, 1487645946, 59984867, 4199882800L, 1844882806, 1989249228, 1277555970, 3623636965L, 3419915562L, 1149249077, 2744104290L, 1514790577, 459744698, 244860394, 3235995134L, 1963115311, 4027744588L, 2544078150L, 4190530515L, 1608975247, 2627016082L, 2062270317, 1507497298, 2200818878L, 567498868, 1764313568, 3359936201L, 2305455554L, 2037970062, 1047239000, 1910319033, 1337376481, 2904027272L, 2892417312L, 984907214, 1243112415, 830661914, 861968209, 2135253587, 2011214180, 2927934315L, 2686254721L, 731183368, 1750626376, 4246310725L, 1820824798, 4172763771L, 3542330227L, 48394827, 2404901663L, 2871682645L, 671593195, 3254988725L, 2073724613, 145085239, 2280796200L, 2779915199L, 1790575107, 2187128086L, 472615631, 3029510009L, 4075877127L, 3802222185L, 4107101658L, 3201631749L, 1646252340, 4270507174L, 1402811438, 1436590835, 3778151818L, 3950355702L, 3963161475L, 4020912224L, 2667994737L, 273792366, 2331590177L, 104699613, 95345982, 3175501286L, 2377486676L, 1560637892, 3564045318L, 369057872, 4213447064L, 3919042237L, 1137477952, 2658625497L, 1119727848, 2340947849L, 1530455833, 4007360968L, 172466556, 266959938, 516552836, 0, 2256734592L, 3980931627L, 1890328081, 1917742170, 4294704398L, 945164165, 3575528878L, 958871085, 3647212047L, 2787207260L, 1423022939, 775562294, 1739656202, 3876557655L, 2530391278L, 2443058075L, 3310321856L, 547512796, 1265195639, 437656594, 3121275539L, 719700128, 3762502690L, 387781147, 218828297, 3350065803L, 2830708150L, 2848461854L, 428169201, 122466165, 3720081049L, 1627235199, 648017665, 4122762354L, 1002783846, 2117360635, 695634755, 3336358691L, 4234721005L, 4049844452L, 3704280881L, 2232435299L, 574624663, 287343814, 612205898, 1039717051, 840019705, 2708326185L, 793451934, 821288114, 1391201670, 3822090177L, 376187827, 3113855344L, 1224348052, 1679968233, 2361698556L, 1058709744, 752375421, 2431590963L, 1321699145, 3519142200L, 2734591178L, 188127444, 2177869557L, 3727205754L, 2384911031L, 3215212461L, 2648976442L, 2450346104L, 3432737375L, 1180849278, 331544205, 3102249176L, 4150144569L, 2952102595L, 2159976285L, 2474404304L, 766078933, 313773861, 2570832044L, 2108100632, 1668212892, 3145456443L, 2013908262, 418672217, 3070356634L, 2594734927L, 1852171925, 3867060991L, 3473416636L, 3907448597L, 2614737639L, 919489135, 164948639, 2094410160, 2997825956L, 590424639, 2486224549L, 1723872674, 3157750862L, 3399941250L, 3501252752L, 3625268135L, 2555048196L, 3673637356L, 1343127501, 4130281361L, 3599595085L, 2957853679L, 1297403050, 81781910, 3051593425L, 2283490410L, 532201772, 1367295589, 3926170974L, 895287692, 1953757831, 1093597963, 492483431, 3528626907L, 1446242576, 1192455638, 1636604631, 209336225, 344873464, 1015671571, 669961897, 3375740769L, 3857572124L, 2973530695L, 3747192018L, 1933530610, 3464042516L, 935293895, 3454686199L, 2858115069L, 1863638845, 3683022916L, 4085369519L, 3292445032L, 875313188, 1080017571, 3279033885L, 621591778, 1233856572, 2504130317L, 24197544, 3017672716L, 3835484340L, 3247465558L, 2220981195L, 3060847922L, 1551124588, 1463996600)
T8 = (4104605777L, 1097159550, 396673818, 660510266, 2875968315L, 2638606623L, 4200115116L, 3808662347L, 821712160, 1986918061, 3430322568L, 38544885, 3856137295L, 718002117, 893681702, 1654886325, 2975484382L, 3122358053L, 3926825029L, 4274053469L, 796197571, 1290801793, 1184342925, 3556361835L, 2405426947L, 2459735317L, 1836772287, 1381620373, 3196267988L, 1948373848, 3764988233L, 3385345166L, 3263785589L, 2390325492L, 1480485785, 3111247143L, 3780097726L, 2293045232L, 548169417, 3459953789L, 3746175075L, 439452389, 1362321559, 1400849762, 1685577905, 1806599355, 2174754046L, 137073913, 1214797936, 1174215055, 3731654548L, 2079897426, 1943217067, 1258480242, 529487843, 1437280870, 3945269170L, 3049390895L, 3313212038L, 923313619, 679998000, 3215307299L, 57326082, 377642221, 3474729866L, 2041877159, 133361907, 1776460110, 3673476453L, 96392454, 878845905, 2801699524L, 777231668, 4082475170L, 2330014213L, 4142626212L, 2213296395L, 1626319424, 1906247262, 1846563261, 562755902, 3708173718L, 1040559837, 3871163981L, 1418573201, 3294430577L, 114585348, 1343618912, 2566595609L, 3186202582L, 1078185097, 3651041127L, 3896688048L, 2307622919L, 425408743, 3371096953L, 2081048481, 1108339068, 2216610296L, 0, 2156299017L, 736970802, 292596766, 1517440620, 251657213, 2235061775L, 2933202493L, 758720310, 265905162, 1554391400, 1532285339, 908999204, 174567692, 1474760595, 4002861748L, 2610011675L, 3234156416L, 3693126241L, 2001430874, 303699484, 2478443234L, 2687165888L, 585122620, 454499602, 151849742, 2345119218L, 3064510765L, 514443284, 4044981591L, 1963412655, 2581445614L, 2137062819, 19308535, 1928707164, 1715193156, 4219352155L, 1126790795, 600235211, 3992742070L, 3841024952L, 836553431, 1669664834, 2535604243L, 3323011204L, 1243905413, 3141400786L, 4180808110L, 698445255, 2653899549L, 2989552604L, 2253581325L, 3252932727L, 3004591147L, 1891211689, 2487810577L, 3915653703L, 4237083816L, 4030667424L, 2100090966, 865136418, 1229899655, 953270745, 3399679628L, 3557504664L, 4118925222L, 2061379749, 3079546586L, 2915017791L, 983426092, 2022837584, 1607244650, 2118541908, 2366882550L, 3635996816L, 972512814, 3283088770L, 1568718495, 3499326569L, 3576539503L, 621982671, 2895723464L, 410887952, 2623762152L, 1002142683, 645401037, 1494807662, 2595684844L, 1335535747, 2507040230L, 4293295786L, 3167684641L, 367585007, 3885750714L, 1865862730, 2668221674L, 2960971305L, 2763173681L, 1059270954, 2777952454L, 2724642869L, 1320957812, 2194319100L, 2429595872L, 2815956275L, 77089521, 3973773121L, 3444575871L, 2448830231L, 1305906550, 4021308739L, 2857194700L, 2516901860L, 3518358430L, 1787304780, 740276417, 1699839814, 1592394909, 2352307457L, 2272556026L, 188821243, 1729977011, 3687994002L, 274084841, 3594982253L, 3613494426L, 2701949495L, 4162096729L, 322734571, 2837966542L, 1640576439, 484830689, 1202797690, 3537852828L, 4067639125L, 349075736, 3342319475L, 4157467219L, 4255800159L, 1030690015, 1155237496, 2951971274L, 1757691577, 607398968, 2738905026L, 499347990, 3794078908L, 1011452712, 227885567, 2818666809L, 213114376, 3034881240L, 1455525988, 3414450555L, 850817237, 1817998408, 3092726480L)
U1 = (0, 235474187, 470948374, 303765277, 941896748, 908933415, 607530554, 708780849, 1883793496, 2118214995, 1817866830, 1649639237, 1215061108, 1181045119, 1417561698, 1517767529, 3767586992L, 4003061179L, 4236429990L, 4069246893L, 3635733660L, 3602770327L, 3299278474L, 3400528769L, 2430122216L, 2664543715L, 2362090238L, 2193862645L, 2835123396L, 2801107407L, 3035535058L, 3135740889L, 3678124923L, 3576870512L, 3341394285L, 3374361702L, 3810496343L, 3977675356L, 4279080257L, 4043610186L, 2876494627L, 2776292904L, 3076639029L, 3110650942L, 2472011535L, 2640243204L, 2403728665L, 2169303058L, 1001089995, 899835584, 666464733, 699432150, 59727847, 226906860, 530400753, 294930682, 1273168787, 1172967064, 1475418501, 1509430414, 1942435775, 2110667444, 1876241833, 1641816226, 2910219766L, 2743034109L, 2976151520L, 3211623147L, 2505202138L, 2606453969L, 2302690252L, 2269728455L, 3711829422L, 3543599269L, 3240894392L, 3475313331L, 3843699074L, 3943906441L, 4178062228L, 4144047775L, 1306967366, 1139781709, 1374988112, 1610459739, 1975683434, 2076935265, 1775276924, 1742315127, 1034867998, 866637845, 566021896, 800440835, 92987698, 193195065, 429456164, 395441711, 1984812685, 2017778566, 1784663195, 1683407248, 1315562145, 1080094634, 1383856311, 1551037884, 101039829, 135050206, 437757123, 337553864, 1042385657, 807962610, 573804783, 742039012, 2531067453L, 2564033334L, 2328828971L, 2227573024L, 2935566865L, 2700099354L, 3001755655L, 3168937228L, 3868552805L, 3902563182L, 4203181171L, 4102977912L, 3736164937L, 3501741890L, 3265478751L, 3433712980L, 1106041591, 1340463100, 1576976609, 1408749034, 2043211483, 2009195472, 1708848333, 1809054150, 832877231, 1068351396, 766945465, 599762354, 159417987, 126454664, 361929877, 463180190, 2709260871L, 2943682380L, 3178106961L, 3009879386L, 2572697195L, 2538681184L, 2236228733L, 2336434550L, 3509871135L, 3745345300L, 3441850377L, 3274667266L, 3910161971L, 3877198648L, 4110568485L, 4211818798L, 2597806476L, 2497604743L, 2261089178L, 2295101073L, 2733856160L, 2902087851L, 3202437046L, 2968011453L, 3936291284L, 3835036895L, 4136440770L, 4169408201L, 3535486456L, 3702665459L, 3467192302L, 3231722213L, 2051518780, 1951317047, 1716890410, 1750902305, 1113818384, 1282050075, 1584504582, 1350078989, 168810852, 67556463, 371049330, 404016761, 841739592, 1008918595, 775550814, 540080725, 3969562369L, 3801332234L, 4035489047L, 4269907996L, 3569255213L, 3669462566L, 3366754619L, 3332740144L, 2631065433L, 2463879762L, 2160117071L, 2395588676L, 2767645557L, 2868897406L, 3102011747L, 3069049960L, 202008497, 33778362, 270040487, 504459436, 875451293, 975658646, 675039627, 641025152, 2084704233, 1917518562, 1615861247, 1851332852, 1147550661, 1248802510, 1484005843, 1451044056, 933301370, 967311729, 733156972, 632953703, 260388950, 25965917, 328671808, 496906059, 1206477858, 1239443753, 1543208500, 1441952575, 2144161806, 1908694277, 1675577880, 1842759443, 3610369226L, 3644379585L, 3408119516L, 3307916247L, 4011190502L, 3776767469L, 4077384432L, 4245618683L, 2809771154L, 2842737049L, 3144396420L, 3043140495L, 2673705150L, 2438237621L, 2203032232L, 2370213795L)
U2 = (0, 185469197, 370938394, 487725847, 741876788, 657861945, 975451694, 824852259, 1483753576, 1400783205, 1315723890, 1164071807, 1950903388, 2135319889, 1649704518, 1767536459, 2967507152L, 3152976349L, 2801566410L, 2918353863L, 2631447780L, 2547432937L, 2328143614L, 2177544179L, 3901806776L, 3818836405L, 4270639778L, 4118987695L, 3299409036L, 3483825537L, 3535072918L, 3652904859L, 2077965243, 1893020342, 1841768865, 1724457132, 1474502543, 1559041666, 1107234197, 1257309336, 598438867, 681933534, 901210569, 1052338372, 261314535, 77422314, 428819965, 310463728, 3409685355L, 3224740454L, 3710368113L, 3593056380L, 3875770207L, 3960309330L, 4045380933L, 4195456072L, 2471224067L, 2554718734L, 2237133081L, 2388260884L, 3212035895L, 3028143674L, 2842678573L, 2724322336L, 4138563181L, 4255350624L, 3769721975L, 3955191162L, 3667219033L, 3516619604L, 3431546947L, 3347532110L, 2933734917L, 2782082824L, 3099667487L, 3016697106L, 2196052529L, 2313884476L, 2499348523L, 2683765030L, 1179510461, 1296297904, 1347548327, 1533017514, 1786102409, 1635502980, 2087309459, 2003294622, 507358933, 355706840, 136428751, 53458370, 839224033, 957055980, 605657339, 790073846, 2373340630L, 2256028891L, 2607439820L, 2422494913L, 2706270690L, 2856345839L, 3075636216L, 3160175349L, 3573941694L, 3725069491L, 3273267108L, 3356761769L, 4181598602L, 4063242375L, 4011996048L, 3828103837L, 1033297158, 915985419, 730517276, 545572369, 296679730, 446754879, 129166120, 213705253, 1709610350, 1860738147, 1945798516, 2029293177, 1239331162, 1120974935, 1606591296, 1422699085, 4148292826L, 4233094615L, 3781033664L, 3931371469L, 3682191598L, 3497509347L, 3446004468L, 3328955385L, 2939266226L, 2755636671L, 3106780840L, 2988687269L, 2198438022L, 2282195339L, 2501218972L, 2652609425L, 1201765386, 1286567175, 1371368976, 1521706781, 1805211710, 1620529459, 2105887268, 1988838185, 533804130, 350174575, 164439672, 46346101, 870912086, 954669403, 636813900, 788204353, 2358957921L, 2274680428L, 2592523643L, 2441661558L, 2695033685L, 2880240216L, 3065962831L, 3182487618L, 3572145929L, 3756299780L, 3270937875L, 3388507166L, 4174560061L, 4091327024L, 4006521127L, 3854606378L, 1014646705, 930369212, 711349675, 560487590, 272786309, 457992840, 106852767, 223377554, 1678381017, 1862534868, 1914052035, 2031621326, 1211247597, 1128014560, 1580087799, 1428173050, 32283319, 182621114, 401639597, 486441376, 768917123, 651868046, 1003007129, 818324884, 1503449823, 1385356242, 1333838021, 1150208456, 1973745387, 2125135846, 1673061617, 1756818940, 2970356327L, 3120694122L, 2802849917L, 2887651696L, 2637442643L, 2520393566L, 2334669897L, 2149987652L, 3917234703L, 3799141122L, 4284502037L, 4100872472L, 3309594171L, 3460984630L, 3545789473L, 3629546796L, 2050466060, 1899603969, 1814803222, 1730525723, 1443857720, 1560382517, 1075025698, 1260232239, 575138148, 692707433, 878443390, 1062597235, 243256656, 91341917, 409198410, 325965383, 3403100636L, 3252238545L, 3704300486L, 3620022987L, 3874428392L, 3990953189L, 4042459122L, 4227665663L, 2460449204L, 2578018489L, 2226875310L, 2411029155L, 3198115200L, 3046200461L, 2827177882L, 2743944855L)
U3 = (0, 218828297, 437656594, 387781147, 875313188, 958871085, 775562294, 590424639, 1750626376, 1699970625, 1917742170, 2135253587, 1551124588, 1367295589, 1180849278, 1265195639, 3501252752L, 3720081049L, 3399941250L, 3350065803L, 3835484340L, 3919042237L, 4270507174L, 4085369519L, 3102249176L, 3051593425L, 2734591178L, 2952102595L, 2361698556L, 2177869557L, 2530391278L, 2614737639L, 3145456443L, 3060847922L, 2708326185L, 2892417312L, 2404901663L, 2187128086L, 2504130317L, 2555048196L, 3542330227L, 3727205754L, 3375740769L, 3292445032L, 3876557655L, 3926170974L, 4246310725L, 4027744588L, 1808481195, 1723872674, 1910319033, 2094410160, 1608975247, 1391201670, 1173430173, 1224348052, 59984867, 244860394, 428169201, 344873464, 935293895, 984907214, 766078933, 547512796, 1844882806, 1627235199, 2011214180, 2062270317, 1507497298, 1423022939, 1137477952, 1321699145, 95345982, 145085239, 532201772, 313773861, 830661914, 1015671571, 731183368, 648017665, 3175501286L, 2957853679L, 2807058932L, 2858115069L, 2305455554L, 2220981195L, 2474404304L, 2658625497L, 3575528878L, 3625268135L, 3473416636L, 3254988725L, 3778151818L, 3963161475L, 4213447064L, 4130281361L, 3599595085L, 3683022916L, 3432737375L, 3247465558L, 3802222185L, 4020912224L, 4172763771L, 4122762354L, 3201631749L, 3017672716L, 2764249623L, 2848461854L, 2331590177L, 2280796200L, 2431590963L, 2648976442L, 104699613, 188127444, 472615631, 287343814, 840019705, 1058709744, 671593195, 621591778, 1852171925, 1668212892, 1953757831, 2037970062, 1514790577, 1463996600, 1080017571, 1297403050, 3673637356L, 3623636965L, 3235995134L, 3454686199L, 4007360968L, 3822090177L, 4107101658L, 4190530515L, 2997825956L, 3215212461L, 2830708150L, 2779915199L, 2256734592L, 2340947849L, 2627016082L, 2443058075L, 172466556, 122466165, 273792366, 492483431, 1047239000, 861968209, 612205898, 695634755, 1646252340, 1863638845, 2013908262, 1963115311, 1446242576, 1530455833, 1277555970, 1093597963, 1636604631, 1820824798, 2073724613, 1989249228, 1436590835, 1487645946, 1337376481, 1119727848, 164948639, 81781910, 331544205, 516552836, 1039717051, 821288114, 669961897, 719700128, 2973530695L, 3157750862L, 2871682645L, 2787207260L, 2232435299L, 2283490410L, 2667994737L, 2450346104L, 3647212047L, 3564045318L, 3279033885L, 3464042516L, 3980931627L, 3762502690L, 4150144569L, 4199882800L, 3070356634L, 3121275539L, 2904027272L, 2686254721L, 2200818878L, 2384911031L, 2570832044L, 2486224549L, 3747192018L, 3528626907L, 3310321856L, 3359936201L, 3950355702L, 3867060991L, 4049844452L, 4234721005L, 1739656202, 1790575107, 2108100632, 1890328081, 1402811438, 1586903591, 1233856572, 1149249077, 266959938, 48394827, 369057872, 418672217, 1002783846, 919489135, 567498868, 752375421, 209336225, 24197544, 376187827, 459744698, 945164165, 895287692, 574624663, 793451934, 1679968233, 1764313568, 2117360635, 1933530610, 1343127501, 1560637892, 1243112415, 1192455638, 3704280881L, 3519142200L, 3336358691L, 3419915562L, 3907448597L, 3857572124L, 4075877127L, 4294704398L, 3029510009L, 3113855344L, 2927934315L, 2744104290L, 2159976285L, 2377486676L, 2594734927L, 2544078150L)
U4 = (0, 151849742, 303699484, 454499602, 607398968, 758720310, 908999204, 1059270954, 1214797936, 1097159550, 1517440620, 1400849762, 1817998408, 1699839814, 2118541908, 2001430874, 2429595872L, 2581445614L, 2194319100L, 2345119218L, 3034881240L, 3186202582L, 2801699524L, 2951971274L, 3635996816L, 3518358430L, 3399679628L, 3283088770L, 4237083816L, 4118925222L, 4002861748L, 3885750714L, 1002142683, 850817237, 698445255, 548169417, 529487843, 377642221, 227885567, 77089521, 1943217067, 2061379749, 1640576439, 1757691577, 1474760595, 1592394909, 1174215055, 1290801793, 2875968315L, 2724642869L, 3111247143L, 2960971305L, 2405426947L, 2253581325L, 2638606623L, 2487810577L, 3808662347L, 3926825029L, 4044981591L, 4162096729L, 3342319475L, 3459953789L, 3576539503L, 3693126241L, 1986918061, 2137062819, 1685577905, 1836772287, 1381620373, 1532285339, 1078185097, 1229899655, 1040559837, 923313619, 740276417, 621982671, 439452389, 322734571, 137073913, 19308535, 3871163981L, 4021308739L, 4104605777L, 4255800159L, 3263785589L, 3414450555L, 3499326569L, 3651041127L, 2933202493L, 2815956275L, 3167684641L, 3049390895L, 2330014213L, 2213296395L, 2566595609L, 2448830231L, 1305906550, 1155237496, 1607244650, 1455525988, 1776460110, 1626319424, 2079897426, 1928707164, 96392454, 213114376, 396673818, 514443284, 562755902, 679998000, 865136418, 983426092, 3708173718L, 3557504664L, 3474729866L, 3323011204L, 4180808110L, 4030667424L, 3945269170L, 3794078908L, 2507040230L, 2623762152L, 2272556026L, 2390325492L, 2975484382L, 3092726480L, 2738905026L, 2857194700L, 3973773121L, 3856137295L, 4274053469L, 4157467219L, 3371096953L, 3252932727L, 3673476453L, 3556361835L, 2763173681L, 2915017791L, 3064510765L, 3215307299L, 2156299017L, 2307622919L, 2459735317L, 2610011675L, 2081048481, 1963412655, 1846563261, 1729977011, 1480485785, 1362321559, 1243905413, 1126790795, 878845905, 1030690015, 645401037, 796197571, 274084841, 425408743, 38544885, 188821243, 3613494426L, 3731654548L, 3313212038L, 3430322568L, 4082475170L, 4200115116L, 3780097726L, 3896688048L, 2668221674L, 2516901860L, 2366882550L, 2216610296L, 3141400786L, 2989552604L, 2837966542L, 2687165888L, 1202797690, 1320957812, 1437280870, 1554391400, 1669664834, 1787304780, 1906247262, 2022837584, 265905162, 114585348, 499347990, 349075736, 736970802, 585122620, 972512814, 821712160, 2595684844L, 2478443234L, 2293045232L, 2174754046L, 3196267988L, 3079546586L, 2895723464L, 2777952454L, 3537852828L, 3687994002L, 3234156416L, 3385345166L, 4142626212L, 4293295786L, 3841024952L, 3992742070L, 174567692, 57326082, 410887952, 292596766, 777231668, 660510266, 1011452712, 893681702, 1108339068, 1258480242, 1343618912, 1494807662, 1715193156, 1865862730, 1948373848, 2100090966, 2701949495L, 2818666809L, 3004591147L, 3122358053L, 2235061775L, 2352307457L, 2535604243L, 2653899549L, 3915653703L, 3764988233L, 4219352155L, 4067639125L, 3444575871L, 3294430577L, 3746175075L, 3594982253L, 836553431, 953270745, 600235211, 718002117, 367585007, 484830689, 133361907, 251657213, 2041877159, 1891211689, 1806599355, 1654886325, 1568718495, 1418573201, 1335535747, 1184342925)
class rijndael:
def __init__(self, key, block_size = 16):
if block_size != 16 and block_size != 24 and block_size != 32:
raise ValueError('Invalid block size: ' + str(block_size))
if len(key) != 16 and len(key) != 24 and len(key) != 32:
raise ValueError('Invalid key size: ' + str(len(key)))
self.block_size = block_size
ROUNDS = num_rounds[len(key)][block_size]
BC = block_size / 4
# encryption round keys
Ke = [[0] * BC for i in xrange(ROUNDS + 1)]
# decryption round keys
Kd = [[0] * BC for i in xrange(ROUNDS + 1)]
ROUND_KEY_COUNT = (ROUNDS + 1) * BC
KC = len(key) / 4
# copy user material bytes into temporary ints
tk = []
for i in xrange(0, KC):
tk.append((ord(key[i * 4]) << 24) | (ord(key[i * 4 + 1]) << 16) |
(ord(key[i * 4 + 2]) << 8) | ord(key[i * 4 + 3]))
# copy values into round key arrays
t = 0
j = 0
while j < KC and t < ROUND_KEY_COUNT:
Ke[t / BC][t % BC] = tk[j]
Kd[ROUNDS - (t / BC)][t % BC] = tk[j]
j += 1
t += 1
tt = 0
rconpointer = 0
while t < ROUND_KEY_COUNT:
# extrapolate using phi (the round key evolution function)
tt = tk[KC - 1]
tk[0] ^= (S[(tt >> 16) & 0xFF] & 0xFF) << 24 ^ \
(S[(tt >> 8) & 0xFF] & 0xFF) << 16 ^ \
(S[ tt & 0xFF] & 0xFF) << 8 ^ \
(S[(tt >> 24) & 0xFF] & 0xFF) ^ \
(rcon[rconpointer] & 0xFF) << 24
rconpointer += 1
if KC != 8:
for i in xrange(1, KC):
tk[i] ^= tk[i-1]
else:
for i in xrange(1, KC / 2):
tk[i] ^= tk[i-1]
tt = tk[KC / 2 - 1]
tk[KC / 2] ^= (S[ tt & 0xFF] & 0xFF) ^ \
(S[(tt >> 8) & 0xFF] & 0xFF) << 8 ^ \
(S[(tt >> 16) & 0xFF] & 0xFF) << 16 ^ \
(S[(tt >> 24) & 0xFF] & 0xFF) << 24
for i in xrange(KC / 2 + 1, KC):
tk[i] ^= tk[i-1]
# copy values into round key arrays
j = 0
while j < KC and t < ROUND_KEY_COUNT:
Ke[t / BC][t % BC] = tk[j]
Kd[ROUNDS - (t / BC)][t % BC] = tk[j]
j += 1
t += 1
# inverse MixColumn where needed
for r in xrange(1, ROUNDS):
for j in xrange(BC):
tt = Kd[r][j]
Kd[r][j] = U1[(tt >> 24) & 0xFF] ^ \
U2[(tt >> 16) & 0xFF] ^ \
U3[(tt >> 8) & 0xFF] ^ \
U4[ tt & 0xFF]
self.Ke = Ke
self.Kd = Kd
def encrypt(self, plaintext):
if len(plaintext) != self.block_size:
raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(plaintext)))
Ke = self.Ke
BC = self.block_size / 4
ROUNDS = len(Ke) - 1
if BC == 4:
SC = 0
elif BC == 6:
SC = 1
else:
SC = 2
s1 = shifts[SC][1][0]
s2 = shifts[SC][2][0]
s3 = shifts[SC][3][0]
a = [0] * BC
# temporary work array
t = []
# plaintext to ints + key
for i in xrange(BC):
t.append((ord(plaintext[i * 4 ]) << 24 |
ord(plaintext[i * 4 + 1]) << 16 |
ord(plaintext[i * 4 + 2]) << 8 |
ord(plaintext[i * 4 + 3]) ) ^ Ke[0][i])
# apply round transforms
for r in xrange(1, ROUNDS):
for i in xrange(BC):
a[i] = (T1[(t[ i ] >> 24) & 0xFF] ^
T2[(t[(i + s1) % BC] >> 16) & 0xFF] ^
T3[(t[(i + s2) % BC] >> 8) & 0xFF] ^
T4[ t[(i + s3) % BC] & 0xFF] ) ^ Ke[r][i]
t = a[:] #copy.copy(a)
# last round is special
result = []
for i in xrange(BC):
tt = Ke[ROUNDS][i]
result.append((S[(t[ i ] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF)
result.append((S[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF)
result.append((S[(t[(i + s2) % BC] >> 8) & 0xFF] ^ (tt >> 8)) & 0xFF)
result.append((S[ t[(i + s3) % BC] & 0xFF] ^ tt ) & 0xFF)
return "".join(map(chr, result))