МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра БІТ
Практична робота № 1 Блоковий шифр DES з навчальної дисципліни: “Прикладна криптологія” Львів – 2011 Завдання Написати програму, яка здійснює шифрування і розшифрування тексту за допомогою блокового шифру DES Теоретичний вступ DES (англ. Data Encryption Standard) — це симетричний алгоритм шифрування даних, стандарт шифрування прийнятий урядом США із 1976 до кінця 1990-х, з часом набув міжнародного застосування. Ще з часу свого розроблення алгоритм викликав неоднозначні відгуки. Оскільки DES містив засекречені елементи своєї структури, породжувались побоювання щодо можливості контролю з боку Національного Агенства Безпеки США (англ. National Security Agency). Алгоритм піддавався критиці за малу довжину ключа, що, врешті, після бурних обговорень та контролю академічної громадськості, не завадило йому стати загальноприйнятим стандартом. DES дав поштовх сучасним уявленням про блочні алгоритми шифрування та криптоаналіз. Зараз DES вважається ненадійним в основному через малу довжину ключа (56 біт) та розмір блоку (64 біти). У 1999 ключ DES було публічно дешифровано за 22 години 15 хвилин. Вважається, що алгоритм достатньо надійний для застосування у модифікації 3-DES, хоча існують розроблені теоретичні атаки. DES поступово витісняється алгоритмом AES, що з 2002 року є стандартом США. Текст програми <html> <head> <meta charset="utf-8"> <title>DES</title> <link rel="stylesheet" type="text/css" title="default" media="screen" href="main.css"> <script type="text/javascript" src="parse.js"></script> </head> <body> <div class="workfield" id="workfield"> <form name="io" method="post" action="des.php"> <input style="float:left" type="text" id="phrase" name="inputPhrase" value=""> <input style="float:left" type="text" id="key" name="key" maxlength="8" value="abcdefgh"> <input type="hidden" id="tmp" value="" /> <input type="submit" name="button" value="DES" class="button" onclick="getValues();"> </form> <?php echo '<div id="output" class="output">'; //1) bin is 64 bit array; //each element of bin is 16bit and represented in binary; //receive data from cookie as arr; $bin = explode(",", $_COOKIE["phraseArrayBin"]); $bin = str_split(implode("",$bin)); $key = explode(",", $_COOKIE["keyArrayBin"]); $key = implode("", $key); //make one string from array; $block = 64; while((sizeof($bin) % $block) != 0) array_push($bin, '0'); echo "<br />Virgin text ___= ";array_show($bin); $arr = array_chunk($bin, $block); $bit = 16; $encr = des($arr, $key, 0); binToDec($encr, $arr, $bit); $decr = des($encr, $key, 1);$dec = binToDec($decr, $arr, $bit); //$asd = "asd"; ?> <script type="text/javascript" > var smth = "<?= join(",", $dec) ?>"; decoded = smth.split(","); for (i = 0; i < decoded.length; i++) decoded[i] = (String.fromCharCode(decoded[i])); output.innerHTML += "<hr />Decoded = " + decoded.join(""); </script> <?php echo '</div>'; function des($arr, $key, $flag){ $result = array(array()); echo $whatWasDone = $flag == 0 ? "<hr />encryptedBin = " : "<br />decryptedBin = "; for ($i = 0; $i < sizeof($arr); $i++){ //1) ip $iped = ip($arr[$i]); $phrase = cypher($iped, $key, $flag); //5) (IP^(-1)) final permutation; $iped_1 = ip_1($phrase); $result[$i] = $iped_1; array_show($result[$i]); } return $result; } function ip($arr){ $iped = array(); $ipOrder = array( "57", "49", "41", "33", "25", "17", "9", "1", "59", "51", "43", "35", "27", "19", "11", "3", "61", "53", "45", "37", "29", "21", "13", "5", "63", "55", "47", "39", "31", "23", "15", "7", "56", "48", "40", "32", "24", "16", "8", "0", "58", "50", "42", "34", "26", "18", "10", "2", "60", "52", "44", "36", "28", "20", "12", "4", "62", "54", "46", "38", "30", "22", "14", "6"); for ($i = 0; $i < sizeof($ipOrder); $i++) $iped[$i] = $arr[$ipOrder[$i]]; return $iped; } function ip_1($arr){ $iped = array(); $ipOrder = array( "39", "7", "47", "15", "55", "23", "63", "31", "38", "6", "46", "14", "54", "22", "62", "30", "37", "5", "45", "13", "53", "21", "61", "29", "36", "4", "44", "12", "52", "20", "60", "28", "35", "3", "43", "11", "51", "19", "59", "27", "34", "2", "42", "10", "50", "18", "58", "26", "33", "1", "41", "9", "49", "17", "57", "25", "32", "0", "40", "8", "48", "16", "56", "24"); for ($i = 0; $i < sizeof($ipOrder); $i++) $iped[$i] = $arr[$ipOrder[$i]]; return $iped; } function cypher($iped, $key, $flag){ //to encrypt text we need: // 1 - 64bit of text; // 2 - (IP) permutate text; // 3 - split it to l&r, so they are 32bit; // 4 - l1 = r0; r1 = f(r0,k0) xor l0; -- 16 iterations; // 5 - (IP^(-1)) final permutation; //$iped is 64bit after permutation; //3) split $iped to L&R; $lr = array(); //to join l&r; $l = array(); $r = array(); $halfsize = sizeof($iped) / 2; for ($i = 0; $i < $halfsize; $i++){ $l[] = $iped[$i]; $r[] = $iped[$i + $halfsize]; } //4.1) generate k; //to generate KEY we need to: // 4.1.1 - expand key from 56 to 64 bits; // 4.1.2 - permutate the expanded key; // 4.1.3 - cycle shift and permutate key 16 times to generate 16 keys; //4.1.1) $keye == expanded key from 56bits to 64bits; $keye = expkey($key); //4.1.2) $keyep == permutated $keye; $keyep = kp($keye); //4.1.3) generate ki; i = 0..15; --the code is below; //4.2) f(r[i], k[i]): //to get f() we need: // 4.2.1 - expand r[i] by E from 32 to 48bits -> $re; // 4.2.2 - kx = expanded_r[i] xor k[i]; Represent temp to B1..8; Each B[i] is 6 bit; // 4.2.3 - Transformation: S(B1..8) = S1..8; Each S[i] is 4 bit; // 4.2.4 - P permutation; $s = array(array(), array(), array(), array(), array(), array(), array(), array()); //to transform kx = B1,,6 to kxs = S1..8, S[i] is 4 bit; $s[0][0] = array("14", "4", "13", "1", "2", "15", "11", "8", "3", "10", "6", "12", "5", "9", "0", "7" ); $s[0][1] = array("0", "15", "7", "4", "14", "2", "13", "1", "10", "6", "12", "11", "9", "5", "3", "8" ); $s[0][2] = array("4", "1", "14", "8", "13", "6", "2", "11", "15", "12", "9", "7", "3", "10", "5", "0" ); $s[0][3] = array("15", "12", "8", "2", "4", "9", "1", "7", "5", "11", "3", "14", "10", "0", "6", "13"); $s[1][0] = array("15", "1", "8", "14", "6", "11", "3", "4", "9", "7", "2", "13", "12", "0", "5", "10"); $s[1][1] = array("3", "13", "4", "7", "15", "2", "8", "14", "12", "0", "1", "10", "6", "9", "11", "5" ); $s[1][2] = array("0", "14", "7", "11", "10", "4", "13", "1", "5", "8", "12", "6", "9", "3", "2", "15"); $s[1][3] = array("13", "8", "10", "1", "3", "15", "4", "2", "11", "6", "7", "12", "0", "5", "14", "9" ); $s[2][0] = array("10", "0", "9", "14", "6", "3", "15", "5", "1", "13", "12", "7", "11", "4", "2", "8" ); $s[2][1] = array("13", "7", "0", "9", "3", "4", "6", "10", "2", "8", "5", "14", "12", "11", "15", "1" ); $s[2][2] = array("13", "6", "4", "9", "8", "15", "3", "0", "11", "1", "2", "12", "5", "10", "14", "7" ); $s[2][3] = array("1", "10", "13", "0", "6", "9", "8", "7", "4", "15", "14", "3", "11", "5", "2", "12"); $s[3][0] = array("7", "13", "14", "3", "0", "6", "9", "10", "1", "2", "8", "5", "11", "12", "4", "15"); $s[3][1] = array("13", "8", "11", "5", "6", "15", "0", "3", "4", "7", "2", "12", "1", "10", "14", "9" ); $s[3][2] = array("10", "6", "9", "0", "12", "11", "7", "13", "15", "1", "3", "14", "5", "2", "8", "4" ); $s[3][3] = array("3", "15", "0", "6", "10", "1", "13", "8", "9", "4", "5", "11", "12", "7", "2", "14"); $s[4][0] = array("2", "12", "4", "1", "7", "10", "11", "6", "8", "5", "3", "15", "13", "0", "14", "9" ); $s[4][1] = array("14", "11", "2", "12", "4", "7", "13", "1", "5", "0", "15", "10", "3", "9", "8", "6" ); $s[4][2] = array("4", "2", "1", "11", "10", "13", "7", "8", "15", "9", "12", "5", "6", "3", "0", "14"); $s[4][3] = array("11", "8", "12", "7", "1", "14", "2", "13", "6", "15", "0", "9", "10", "4", "5", "3" ); $s[5][0] = array("12", "1", "10", "15", "9", "2", "6", "8", "0", "13", "3", "4", "14", "7", "5", "11"); $s[5][1] = array("10", "15", "4", "2", "7", "12", "9", "5", "6", "1", "13", "14", "0", "11", "3", "8" ); $s[5][2] = array("9", "14", "15", "5", "2", "8", "12", "3", "7", "0", "4", "10", "1", "13", "11", "6" ); $s[5][3] = array("4", "3", "2", "12", "9", "5", "15", "10", "11", "14", "1", "7", "6", "0", "8", "13"); $s[6][0] = array("4", "11", "2", "14", "15", "0", "8", "13", "3", "12", "9", "7", "5", "10", "6", "1" ); $s[6][1] = array("13", "0", "11", "7", "4", "9", "1", "10", "14", "3", "5", "12", "2", "15", "8", "6" ); $s[6][2] = array("1", "4", "11", "13", "12", "3", "7", "14", "10", "15", "6", "8", "0", "5", "9", "2" ); $s[6][3] = array("6", "11", "13", "8", "1", "4", "10", "7", "9", "5", "0", "15", "14", "2", "3", "12"); $s[7][0] = array("13", "2", "8", "4", "6", "15", "11", "1", "10", "9", "3", "14", "5", "0", "12", "7" ); $s[7][1] = array("1", "15", "13", "8", "10", "3", "7", "4", "12", "5", "6", "11", "0", "14", "9", "2" ); $s[7][2] = array("7", "11", "4", "1", "9", "12", "14", "2", "0", "6", "10", "13", "15", "3", "5", "8" ); $s[7][3] = array("2", "1", "14", "7", "4", "10", "8", "13", "15", "12", "9", "0", "3", "5", "6", "11"); //permutation after S transformation in f ->//step4.2.4; $p = array( "15", "6", "19", "20", "28", "11", "27", "16", "0", "14", "22", "25", "4", "17", "30", "9", "1", "7", "23", "13", "31", "26", "2", "8", "18", "12", "29", "5", "21", "10", "3", "24"); //$k = generateKi($keyep); // ----------------Ki generation----------------------------------------------- $k = array(array()); $kx = array(array()); //xored key; for 4.2.2; $kxs = array(array()); //xored and transformed by S key; for 4.2.3; $kxsp = array(array()); //xored and transformed, and permutated; for 4.2.4; $cd = array(); //to join $c and $d; //split $keyep to c & d; $halfsize = sizeof($keyep) / 2; for ($i = 0; $i < $halfsize; $i++){ $c[$i] = $keyep[$i]; $d[$i] = $keyep[$i + $halfsize]; } //shift array $shiftNumber = array("1", "1", "2", "2", "2", "2", "2", "2", "1", "2", "2", "2", "2", "2", "2", "1"); //$h -- permutation after every cycleShift to generate Ki; $h = array( "13", "16", "10", "23", "0", "4", "2", "27", "14", "5", "20", "9", "22", "18", "11", "3", "25", "7", "15", "6", "26", "19", "12", "1", "40", "51", "30", "36", "46", "54", "29", "39", "50", "44", "32", "47", "43", "48", "38", "55", "33", "52", "45", "41", "49", "35", "28", "31"); //should get 16 key by shifting and using $h; // 4.1.3) cycle shift and permutate key 16 times to generate 16 keys; for($i = 0; $i < 16; $i++){ $c = cycleShift($c, $shiftNumber[$i]); $d = cycleShift($d, $shiftNumber[$i]); // $c, $d for $h for ($j = 0; $j < sizeof($c); $j++){ $cd[$j] = $c[$j]; $cd[$j + sizeof($c)] = $d[$j]; } //permutation for ($j = 0; $j < sizeof($h); $j++) $k[$i][$j] = $cd[$h[$j]]; } for($i = 0; $i < 16; $i++){ if ($flag == 0){ //4.2.1) $re = expanded r0; $re = exp_r($r); //4.2.2) B1..8 = xor($re, $k); $kx[$i] = _xor($re, $k[$i]); } else{ //4.2.1) $re = expanded r0; $le = exp_r($l); //4.2.2) B1..8 = xor($re, $k); $kx[$i] = _xor($le, $k[(sizeof($k) - 1) - $i]); } //4.2.3) Transformation: kx = B1..6 to kxs = S1..8; $block = 6; $temp = null; for ($j = 0; $j < sizeof($kx[$i]); $j += $block){ $first = $kx[$i][$j]; $last = $kx[$i][$j + ($block-1)]; $middle = null; for ($q = 1; $q < ($block - 1); $q++) $middle .= $kx[$i][$q + $j]; //echo '<br />$middle = '.$middle; $x = bindec($first.$last); $y = bindec($middle); $index = $j / $block; $temp .= str_pad(decbin($s[$index][$x][$y]), $block, '0', STR_PAD_LEFT); } $kxs[$i] = str_split($temp); //4.2.4) P permutation; for ($j = 0; $j < sizeof($p); $j++) $kxsp[$i][$j] = $kxs[$i][$p[$j]]; if ($flag == 0){ //4) l1 = r0; r1 = f(r0,k0) xor l0; -- 16 iterations; $temp = $l; $l = $r; $r = _xor($kxsp[$i], $temp); } else{ //4) r1 = l0; l1 = f(l0,k0) xor r0; -- 16 iterations; $temp = $r; $r = $l; $l = _xor($kxsp[$i], $temp); } } //--------------------------------------------------------------------- for ($i = 0; $i < sizeof($l); $i++){ $lr[$i] = $l[$i]; $lr[$i + sizeof($r)] = $r[$i]; } return $lr; } function exp_r($bin){ $expanded = array(); $e = array( "31", "0", "1", "2", "3", "4", "3", "4", "5", "6", "7", "8", "7", "8", "9", "10", "11", "12", "11", "12", "13", "14", "15", "16", "15", "16", "17", "18", "19", "20", "19", "20", "21", "22", "23", "24", "23", "24", "25", "26", "27", "28", "27", "28", "29", "30", "31", "0"); for ($i = 0; $i < sizeof($e); $i++) $expanded[$i] = $bin[$e[$i]]; return $expanded; } //if count of "1" in 7 bits is not even add "1" as 8-th bit; else add "0" as 8th bit; function expkey($key){ //$key == 56 bit $key = str_split($key, 7); //make 7 bit array; //echo '<br>newkey = '; array_show($key); //echo '<br>sizeof($key) = '.sizeof($key); for ($i = 0; $i < sizeof($key); $i++){ $temp = str_split($key[$i], 1); $s = 0; //echo '<br>$temp['.$i.'] = '; array_show($temp); for($j = 0; $j < sizeof($temp); $j++) $s += $temp[$j]; if ($s % 2 == 0) $key[$i] .= 1; else $key[$