GetInfo.Ru – Компьютерная библиотека
Последние поступления
Как выбрать систему управления базы данных
Базы данных03/09/14
Этапы загрузки UNIX (в схеме)
Unix27/03/12
Gatewall Antispam: тотальный контроль электронной почты
Спам21/04/11
Мастер-класс: создаем Интернет-магазин (Часть 1)
Обзоры ПО20/04/11
CorelDRAW Graphics Suite X5: Что нового?
Обзоры ПО20/07/10
Добавить статью
Самые читаемые материалы
Часто задаваемые вопросы конференции RU.CRYPT(24031)
Криптография: зачем это нужно(10038)
Почему криптосистемы ненадежны?(9818)
Криптографический алгоритм DersCrypt(4414)
Криптографический алгоритм DersCrypt (версия 1.0)(4179)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Криптография » Криптографический алгоритм DersCrypt

Криптографический алгоритм DersCrypt


Сергей Деревяго
derevyago@yahoo.com
http://ders.stml.net/

Введение

DersCrypt -- это блочный симметричный криптографический алгоритм, построенный на неиспользовавшихся ранее принципах. Суть работы алгоритма состоит в переводе числа из одной системы счисления в другую, перестановке "цифр" и обратном переводе в исходную систему счисления.

DersCrypt обладает следующими достоинствами:

  1. Нет ограничений на длину ключа.
  2. Криптоалгоритм предельно прост для понимания и реализации.
  3. Криптоалгоритм является открытым и свободным для использования. Я являюсь его изобретателем и утверждаю: криптоалгоритм предназначен для свободного использования.
Недостатки DersCrypt:
  1. Стойкость алгоритма серьезно не исследовалась и, следовательно, не доказана.
    (Тем не менее, базовый анализ и статистические эксперименты вполне обнадеживают.)
  2. Длина зашифрованного текста всегда превышает длину исходного текста для шифрования.
    (Приращение порядка удвоенной длины ключа, что вряд ли является неприемлемым там, где оно вообще допустимо.)
  3. Существует ограничение на минимальную длину текста для шифрования.
    (Ограничение не является чрезмерно обременительным, например для 256-битного ключа минимальный объем текста составляет 1920 байт.)
  4. Математически строгое, независимое от реализации определение криптоалгоритма временно отсутствует.
    (Тем не менее, представленная эталонная реализация однозначно определяет алгоритм и безусловно обладает большей практической полезностью.).

Суть криптоалгоритма

Как уже было сказано, суть работы криптоалгоритма состоит в переводе числа из одной системы счисления в другую, перестановке "цифр" и обратном переводе в исходную систему счисления.

Рассмотрим следующий пример. Путь нам необходимо зашифровать текст из четырех букв: a, b, c и d. Выбранным буквам соответствуют байты со значениями 0x61, 0x62, 0x63, 0x64 в шестнадцатеричной системе счисления, поэтому всю строку "abcd" можно рассматривать как одно число 0x61626364, что эквивалентно 1633837924 в обычной десятичной система счисления. Переставим цифры числа 1633837924 согласно перестановке (5,8,7,6,9,0,3,2,1,4):

Исходная позиция:  0 1 2 3 4 5 6 7 8 9
Новая позиция:  5 8 7 6 9 0 3 2 1 4
Исходная цифра:  1 6 3 3 8 3 7 9 2 4
Итоговая цифра:  3 2 9 7 4 1 3 3 6 8

и получим число 3297413368, что эквивалентно 0xC48A88F8. Это число и является результатом шифрования, т.е. по исходной последовательности байт 0x61, 0x62, 0x63, 0x64 мы получили 0xC4, 0x8A, 0x88, 0xF8. Как можно видеть, в результате шифрования из 32 бит изменилось 18: x1x00x0x xxx0x010 xxx0x0xx x11xxx00, что весьма близко к 50%.

Итак, базовый алгоритм DersCrypt состоит из следующих шагов:

  1. Текст для шифрования рассматривается как неотрицательное число A1 в некоторой системе счисления S1 по основанию B1.
  2. Число A1 переводится в другую систему счисления S2 по основанию B2. Число B2 является ключом.
  3. Цифры числа A1 в системе счисления S2 переставляются, в результате чего получается число A2. Перестановка задается значением ключа.
  4. Число A2 переводится в исходную систему счисления S1.
  5. Число A2 в системе счисления S1 и является результатом шифрования.
Или применительно к приведенному выше примеру:
  1. Текст для шифрования -- это последовательность байт 0x61, 0x62, 0x63, 0x64, соответствующая строке "abcd". Число A1 -- это 0x61626364 в шестнадцатеричной системе счисления, т.е. B1=16.
  2. Число A1 в десятичной системе счисления (т.е. B2=10) -- это 1633837924.
  3. Применяя перестановку (5,8,7,6,9,0,3,2,1,4) к цифрам 1,6,3,3,8,3,7,9,2,4 получим число A2=3297413368.
  4. Число A2 в шестнадцатеричной системе счисления -- это 0xC48A88F8.
  5. Таким образом, результатом шифрования является последовательность байт 0xC4, 0x8A, 0x88, 0xF8.
К сожалению, базовый алгоритм DersCrypt сам по себе непригоден к практическому применению в силу существования следующих эффективных способов атаки:
  1. Если зашифровать два числа, отличающихся только значением младшего бита, то разность зашифрованных чисел, очевидно, будет равна B2n для некоторого n. Применительно к нашему примеру: A1=1633837924, A'1=1633837925 и A2=3297413368, A'2=3297513368. Как можно видеть, A2-A'2=-100000, т.е. 105.
  2. Существует и более эффективный способ атаки: Max Alekseyev указал на то, что имея число A1 в системе счисления по основанию B2 и число A2, полученное из A1 произвольной перестановкой цифр, разность A1-A2 всегда делится на B2-1. Например, нетрудно видеть, что 1633837924-3297413368=-1663575444 делится на 9.
Таким образом, DersCrypt не должен сводиться к простой перестановке цифр в некоторой системе счисления. Решение достаточно очевидно: перед применением базового алгоритма, число A1 превращается в некоторое число A'1 посредством приписывания к A1 некоторого количества случайных байт слева и справа. После дешифрования приписанные байты достаточно просто отбросить, получив исходное число A1.

В силу того, что действительно случайные байты довольно сложно получить на практике, в DersCrypt используется предварительное шифрование числа A1 базовым алгоритмом и извлечение из полученного числа A2 последовательности бит нужной длины. На самом деле, для учета значения предыдущего зашифрованного блока текста, процедура формирования псевдослучайной битовой последовательности чуть более усложнена. Ознакомиться с ней можно непосредственно по коду эталонной реализации, комментарии к которой являются неотъемлемой частью описания алгоритма.

Эталонная реализация

Представленная ниже эталонная реализация DersCrypt определяет алгоритм и предназначена для практического исследования его свойств.

Для наибольшего удобства неискушенных в программировании пользователей, использующих разнообразные платформы, языком реализации выбрана Java, а исходный код оформлен исходя из упрощения понимания, а не производительности и/или простоты включения во внешние проекты. Для реального использования предназначены реализации, следующие далее.

Компиляция и запуск

Исходный код для компиляции доступен по следующей ссылке: DersCrypt.java. Для его компиляции нужно набрать в командной строке:
javac DersCrypt.java
После чего в текущем каталоге должен появиться результат компиляции DersCrypt.class.

Для шифрования файла plain_file с использованием ключа key_file:
java DersCrypt e key_file plain_file encr_file
Результат будет помещен в encr_file.

Для дешифрования файла encr_file с использованием ключа key_file:
java DersCrypt d key_file encr_file decr_file
Результат будет помещен в decr_file и должен полностью совпадать с исходным файлом plain_file.

Создание ключа

В качестве ключа можно использовать любой файл размером 16-64 байта (т.е. 128-512 бит), удовлетворяющий следующим условиям:
  1. Первый байт файла не является нулевым, т.е. его значение не равно 0x00. Не следует путать нулевой байт с символом '0', чье значение 0x30 вполне подходит.
  2. Последний байт файла имеет нечетное значение, т.е. наименьший значащий бит этого байта не равен нулю.
Для реального использования вполне подойдет более-менее случайный файл длиной 32 байта (256 бит). Например, для его получения можно 255 раз подбросить монетку (последний 256-й бит всегда равен 1) или 99 раз игральную кость.

Для упрощения создания ключа мной была написана утилита KeyGen.java. Ее компиляция и запуск выполняются следующими командами:
javac KeyGen.java
java KeyGen key_file
после чего KeyGen запросит длину ключа в битах, максимальное значение, а также серию значений для генерации ключа. Например:

  • Если мы хотим создать 256-битный ключ key_file1 с помощью подбрасывания монеты, то диалог будет выглядеть следующим образом:
    java KeyGen key_file1
    Enter key length in bits (128-512): 256
    Enter maximum value (2-65536): 2
    
    [1 of 255] enter value (1-2): 1
    [2 of 255] enter value (1-2): 2
    [3 of 255] enter value (1-2): 2
    ...
    [255 of 255] enter value (1-2): 1
    
    key_file1 file created!
  • Аналогично, 128-битный ключ key_file2 с помощью бросания игральной кости создается посредством:
    java KeyGen key_file2
    Enter key length in bits (128-512): 128
    Enter maximum value (2-65536): 6
    
    [1 of 50] enter value (1-6): 6
    [2 of 50] enter value (1-6): 1
    [3 of 50] enter value (1-6): 3
    ...
    [50 of 50] enter value (1-6): 5
    
    key_file2 file created!

Комментарии к реализации

Ниже приводится исходный код с пронумерованными комментариями.

DersCrypt.java

import java.io.EOFException;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.RandomAccessFile;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * This is the reference implementation of DersCrypt symmetric-key block cipher.
 *
 * @see <a href="http://ders.stml.net/crypt/derscrypt/derscrypt.html">Crypto
 * algorithm DersCrypt</a> -- DersCrypt home page.
 * @version 1.1 2005-12-24
 * @author Sergey P. Derevyago
 */
public final class DersCrypt
{
 /**
  * Encrypts <code>in</code> and writes the result to <code>out</code>.
  *
  * @param key key to use
  * @param in stream to read plain text from
  * @param out stream to write encrypted text to
  * @return number of bytes read from <code>in</code>
  * @throws Exception in case of errors
  */
 public static long streamEncrypt(byte[] key, InputStream in, OutputStream out)
   throws Exception
 {
  long readCnt=0;
  int minLen=minBlockLength(key.length);

  byte[] buf1=readMax(in, minLen);
  readCnt+=buf1.length;

  for (byte[] prevEncr=null; buf1.length>0; ) {
      byte[] plain, buf2=readMax(in, minLen);
      readCnt+=buf2.length;

      if (buf2.length==minLen) {  // [1]
         plain=buf1;
         buf1=buf2;
      }
      else {
           plain=new byte[buf1.length+buf2.length];
           System.arraycopy(buf1, 0, plain, 0, buf1.length);
           System.arraycopy(buf2, 0, plain, buf1.length, buf2.length);

           buf1=new byte[0];
      }

      byte[] encr=blockEncrypt(key, plain, prevEncr);  // [2]
      prevEncr=encr;

      writeInt16(out, encr.length);  // [3]
      out.write(encr);
  }

  return readCnt;
 }

 /**
  * Decrypts <code>in</code> and writes the result to <code>out</code>.
  *
  * @param key key to use
  * @param in stream to read encrypted text from
  * @param out stream to write decrypted text to
  * @return number of bytes read from <code>in</code>
  * @throws Exception in case of errors
  */
 public static long streamDecrypt(byte[] key, InputStream in, OutputStream out)
   throws Exception
 {
  long readCnt=0;
  int minLen=minBlockLength(key.length);

  String errMsg="Invalid data: Invalid block format";
  byte[] prevEncr=null;

  for (int len; (len=readInt16(in))!=-1; ) {
      readCnt+=2;
      if (len<=minLen || len>=minLen*3) throw new Exception(errMsg);  // [4]

      byte[] encr=readMax(in, len);
      readCnt+=encr.length;

      if (encr.length!=len) throw new Exception(errMsg);  // [5]

      byte[] decr=blockDecrypt(key, encr, prevEncr);
      prevEncr=encr;

      out.write(decr);
  }

  return readCnt;
 }

 /**
  * Encrypts a block of plain text.
  *
  * @param key key to use
  * @param plain block of plain text to encrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @return encrypted block
  * @throws Exception in case of errors
  */
 public static byte[] blockEncrypt(byte[] key, byte[] plain, byte[] prevEncr)
   throws Exception
 {
  BigInteger b2=new BigInteger(1, key);  // [6]
  byte[] hash=computeHash(key.length, b2, plain, prevEncr);

  BigInteger aPr1=new BigInteger(1, appendHash(plain, hash));  // [7]

  boolean[] substOne=new boolean[1];
  BigInteger aPr2=basicEncrypt(b2, aPr1, substOne);
  byte[] encr=stripLeadingZeros(aPr2.toByteArray());  // [8]

  if (substOne[0] && blockDecryptImpl(key, encr, prevEncr, false)!=null) {
     throw new Exception("Cannot encrypt this data using this key: "+
       "Hash collision");  // [9]
  }

  return encr;
 }

 /**
  * Decrypts a block of encrypted text.
  *
  * @param key key to use
  * @param encr block of encrypted text to decrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @return decrypted block
  * @throws Exception in case of errors
  */
 public static byte[] blockDecrypt(byte[] key, byte[] encr, byte[] prevEncr)
   throws Exception
 {
  byte[] decr=blockDecryptImpl(key, encr, prevEncr, false);  // [10]
  if (decr!=null) return decr;

  decr=blockDecryptImpl(key, encr, prevEncr, true);  // [11]
  if (decr==null)
     throw new Exception("Incorrect key and/or data: Hash mismatch");  // [12] [13]

  return decr;
 }

 /**
  * Decrypts a block of encrypted text performing the substitution if requested.
  *
  * @param key key to use
  * @param encr block of encrypted text to decrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @param substOne <code>true</code> if the most significant remainder of value
  *        1 must be substituted with 0
  * @return decrypted block or <code>null</code>
  */
 public static byte[] blockDecryptImpl(byte[] key, byte[] encr, byte[] prevEncr,
   boolean substOne)
 {
  BigInteger aPr2=new BigInteger(1, encr), b2=new BigInteger(1, key);

  BigInteger aPr1=basicDecrypt(b2, aPr2, substOne);
  if (aPr1==null) return null;  // [14]

  byte[] decr=stripLeadingZeros(aPr1.toByteArray());  // [15]

  byte[][] ph=extractHash(decr, key.length);
  byte[] plain=ph[0], hash=ph[1];

  byte[] hash2=computeHash(key.length, b2, plain, prevEncr);
  if (!Arrays.equals(hash, hash2)) return null;

  return plain;
 }

 /**
  * Basic encryption functionality.
  *
  * @param b2 key value to use
  * @param a1 number to encrypt
  * @param substOne output parameter, <code>true</code> if the most significant
  *        remainder of value 0 was substituted with 1
  * @return encrypted number
  */
 public static BigInteger basicEncrypt(BigInteger b2, BigInteger a1,
   boolean[] substOne)
 {
  BigInteger[] rems=computeRemainders(a1, b2);
  BigInteger[] rems2=permute(rems, b2, false);

  if (rems2[0].equals(BigInteger.ZERO)) {  // [16]
     rems2[0]=BigInteger.ONE;
     substOne[0]=true;
  }
  else substOne[0]=false;

  BigInteger a2=computeNumber(rems2, b2);
  return a2;
 }
 
 /**
  * Basic decryption functionality.
  *
  * @param b2 key value to use
  * @param a2 number to decrypt
  * @param substOne <code>true</code> if the most significant remainder of value
  *        1 must be substituted with 0 
  * @return decrypted number
  */
 public static BigInteger basicDecrypt(BigInteger b2, BigInteger a2,
   boolean substOne)
 {
  BigInteger[] rems=computeRemainders(a2, b2);

  if (substOne) {  // [17]
     if (rems[0].equals(BigInteger.ONE)) rems[0]=BigInteger.ZERO;
     else return null;
  }

  BigInteger[] rems2=permute(rems, b2, true);
  BigInteger a1=computeNumber(rems2, b2);
  return a1;
 }

 /**
  * Returns minimal data block length required for passed key length. [18]
  *
  * @param keyLength key length
  * @return minimal data block length
  */
 public static int minBlockLength(int keyLength)
 {
  if (keyLength<16) keyLength=16;       // 128->40
  else if (keyLength>64) keyLength=64;  // 512->100

  int n=40+((keyLength-16)*5+2)/4;
  return keyLength*n;
 }

 /**
  * Checks passed parameters.
  *
  * @param key key to check
  * @param length data length to check
  * @throws Exception in case of failed conditions
  */
 public static void check(byte[] key, long length) throws Exception
 {
  if (key[0]==0)
     throw new Exception("Suspectable key: Leading zeros are useless");  // [19]

  if ((key[key.length-1]&1)==0)
     throw new Exception("Suspectable key: Even values are not recommended");  // [20]

  int min=minBlockLength(key.length);
  if (length<min) {
     throw new Exception("Invalid data length: At least "+min+
       " bytes are required");  // [21]
  }
 }

 /**
  * Splits <code>a</code> into a sequence of remainders of division by
  * <code>b</code>.
  *
  * @param a number to split
  * @param b number to divide by
  * @return array of remainders
  */
 public static BigInteger[] computeRemainders(BigInteger a, BigInteger b)
 {
  LinkedList lst=new LinkedList();

  while (!a.equals(BigInteger.ZERO)) {  // [22]
        BigInteger[] qr=a.divideAndRemainder(b);
        a=qr[0];
        lst.addFirst(qr[1]);
  }

  return (BigInteger[])lst.toArray(new BigInteger[lst.size()]);
 }

 /**
  * Converts a sequence of remainders of division by <code>b</code> into a
  * number.
  *
  * @param rems array of remainders
  * @param b number to multiply by
  * @return computed number
  */
 public static BigInteger computeNumber(BigInteger[] rems, BigInteger b)
 {
  BigInteger a=rems[0];

  for (int i=1; i<rems.length; i++) {
      a=a.multiply(b);
      a=a.add(rems[i]);
  }

  return a;
 }
 
 /**
  * Computes hash of a data block. [23]
  *
  * @param len length of hash to compute
  * @param b2 key value to use
  * @param data data block to compute hash from
  * @param prevData previously processed block or <code>null</code>
  * @return computed hash
  */
 public static byte[] computeHash(int len, BigInteger b2, byte[] data,
   byte[] prevData)
 {
  byte[] bits;
  if (prevData!=null) bits=extractBits(prevData, len);
  else {
       bits=new byte[len];
       for (int i=0; i<len; i++) bits[i]=0x55;  // [24]
  }
  
  byte[] prevHash=permuteBits(bits, b2);

  BigInteger a1=new BigInteger(1, appendHash(data, prevHash));
  BigInteger a2=basicEncrypt(b2, a1, new boolean[1]);
  byte[] encr=stripLeadingZeros(a2.toByteArray());

  byte[] hash=permuteBits(extractBits(encr, len), b2);
  if (hash[0]==0) hash[0]=1;  // [25]

  return hash;
 }
 
 /**
  * Appends <code>hash</code> bytes to <code>data</code>. <code>hash</code>
  * array is split into two parts and <code>data</code> is inserted between
  * them.
  *
  * @param data data to append hash to
  * @param hash hash to append
  * @return computed array
  */
 public static byte[] appendHash(byte[] data, byte[] hash)
 {
  byte[] ret=new byte[data.length+hash.length];

  int len=hash.length, mid=len/2;
  System.arraycopy(hash, 0, ret, 0, len-mid);  // [26]
  System.arraycopy(data, 0, ret, len-mid, data.length);
  System.arraycopy(hash, len-mid, ret, ret.length-mid, mid);

  return ret;
 }

 /**
  * Splits passed array into the data and hash parts.
  *
  * @param bytes array to split
  * @param hashLen hash length
  * @return two-elements array with data and hash
  */
 public static byte[][] extractHash(byte[] bytes, int hashLen)
 {
  byte[] data=new byte[bytes.length-hashLen];
  byte[] hash=new byte[hashLen];

  int mid=hashLen/2;
  System.arraycopy(bytes, 0, hash, 0, hashLen-mid);
  System.arraycopy(bytes, hashLen-mid, data, 0, data.length);
  System.arraycopy(bytes, bytes.length-mid, hash, hashLen-mid, mid);

  return new byte[][]{data, hash};
 }

 /**
  * Strips leading zeros out of <code>bytes</code> array.
  *
  * @param bytes array to process
  * @return processed array
  */
 public static byte[] stripLeadingZeros(byte[] bytes)
 {
  if (bytes[0]!=0) return bytes;

  int i;
  for (i=1; i<bytes.length && bytes[i]==0; i++)
      ;

  return subArray(bytes, i, bytes.length-i);
 }

 /**
  * Extracts bits from passed <code>data</code>.
  *
  * @param data data to extract bits from
  * @param bitsLen length of array to return
  * @return computed array
  */
 public static byte[] extractBits(byte[] data, int bitsLen)
 {
  byte[] ret=new byte[bitsLen];

  for (int i=0, j=1; i<bitsLen; i++) {
      for (int mask=0x80; mask!=0; mask>>=1) {
          int n=(j++)*(data.length*8-1)/(bitsLen*8+1);  // [27]
          if ((data[n/8]&BIT_MASKS[n%8])!=0)
             ret[i]|=mask;
      }
  }

  return ret;
 }
 
 /**
  * Creates permutation of passed length. [28]
  *
  * @param len length of permutation
  * @param b number to create permutation from
  * @return array of positions
  */
 public static int[] createPermutation(int len, BigInteger b)
 {
  BigInteger b2=b;
  int[] ret=new int[len], val=new int[len];

  int med=len-len/2;
  for (int i=0; i<len; i++) {  // [29]
      ret[i]=-2;  // [30]

      int pos= (i<med) ? len-med+i : i-med;
      val[pos]=i;
  }

  int[] points={0, len-med, len};

  for (int p=0; p<points.length-1; p++) {  // [31]
      int pbeg=points[p], plen=points[p+1]-pbeg;

     loop:
      for (int i=0, sub=0; i<plen; i++) {
          if (i==plen-2 && sub==0) {  // don't left last element alone [32]
             for (int j=0; ; j++) {
                 if (ret[pbeg+j]==-2) {
                    if (ret[pbeg+j+1]==-2) {  // [33]
                       ret[pbeg+j]=val[pbeg+i+1];
                       ret[pbeg+j+1]=val[pbeg+i];
                       break loop;
                    }

                    break;
                 }
             }
          }

          BigInteger div=BigInteger.valueOf(plen-i-sub);
          if (b2.compareTo(div)<0) b2=b;  // restart from b [34]

          BigInteger[] qr=b2.divideAndRemainder(div);
          b2=qr[0];
          int rem=qr[1].intValue();

          for (int j=0, k=-1, v=val[pbeg+i]; ; j++) {
              if (ret[pbeg+j]==-2 && !(j>0 && v==ret[pbeg+j-1]+1) && ++k==rem) {
                 ret[pbeg+j]=v;
                 sub= (j+1<plen && ret[pbeg+j+1]==-2) ? 1 : 0;  // [35]

                 break;
              }
          }
      }
  }

  return ret;
 }

 /**
  * Permutes passed array of BigIntegers.
  *
  * @param rems array to permute
  * @param b number to create permutation from
  * @param inverse <code>true</code> if inverse permutation must be applied
  * @return permutted array
  */
 public static BigInteger[] permute(BigInteger[] rems, BigInteger b,
   boolean inverse)
 {
  int len=rems.length;
  BigInteger[] ret=new BigInteger[len];

  int perm[]=createPermutation(len, b);
  if (inverse) for (int i=0; i<len; i++) ret[i]=rems[perm[i]];
  else for (int i=0; i<len; i++) ret[perm[i]]=rems[i];

  return ret;
 }

 /**
  * Permutes bits of passed array.
  *
  * @param bits array to permute bits of
  * @param b number to create permutation from
  * @return permutted array
  */
 public static byte[] permuteBits(byte[] bits, BigInteger b)
 {
  byte[] ret=new byte[bits.length];

  int perm[]=createPermutation(bits.length*8, b);
  for (int i=0, j=0; i<bits.length; i++) {
      for (int mask=0x80; mask!=0; mask>>=1) {
          int n=perm[j++];
          if ((bits[i]&mask)!=0) ret[n/8]|=BIT_MASKS[n%8];
      }
  }

  return ret;
 }

 /**
  * Creates a subarray from passed array.
  *
  * @param array array to copy from
  * @param pos position to start from
  * @param len length of subarray
  * @return created subarray
  */
 public static byte[] subArray(byte[] array, int pos, int len)
 {
  byte[] ret=new byte[len];
  System.arraycopy(array, pos, ret, 0, len);

  return ret;
 }

 /**
  * Reads limited number of bytes. 
  *
  * @param in stream to read from
  * @param maxLen maximum number of bytes to read
  * @return read bytes
  * @throws Exception in case of errors
  */
 public static byte[] readMax(InputStream in, int maxLen) throws Exception
 {
  byte[] buf=new byte[maxLen];
  int cnt=in.read(buf);

  if (cnt==buf.length) return buf;
  if (cnt==-1) return new byte[0];
  return subArray(buf, 0, cnt);
 }

 /**
  * Writes 16 bit integer to stream using big-endian byte ordering.
  *
  * @param out stream to write to
  * @param val value to write
  * @throws Exception in case of errors
  */
 public static void writeInt16(OutputStream out, int val) throws Exception
 {
  out.write((val>>>8)&0xFF);
  out.write(val&0xFF);
 }

 /**
  * Reads 16 bit integer from stream using big-endian byte ordering.
  *
  * @param in stream to read from
  * @return read value or <code>-1</code> in case of EOF
  * @throws Exception in case of errors
  */
 public static int readInt16(InputStream in) throws Exception
 {
  int ch1=in.read();
  if (ch1==-1) return -1;

  int ch2=in.read();
  if (ch2==-1) throw new EOFException();

  return (ch1<<8)+ch2;
 }

 /** array of masks to extract successive bits of byte from left to right */
 public static final int[] BIT_MASKS={
   0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
 };

 /**
  * The main function.
  * Checks passed parameters and performs requested operation.
  */
 public static void main(String[] args) throws Exception
 {
  if (args.length!=4) invalidArgs();

  String sCmd=args[0];
  String sKey=args[1];
  String sIn=args[2];
  String sOut=args[3];

  if ( !("e".equals(sCmd) || "d".equals(sCmd)) ) invalidArgs();

  byte[] key=readFile(sKey);
  check(key, (new File(sIn)).length());  // [36]

  FileInputStream fin=new FileInputStream(sIn);
  FileOutputStream fout=new FileOutputStream(sOut);

  long start=System.currentTimeMillis();

  long cnt= ("e".equals(sCmd)) ?
    streamEncrypt(key, fin, fout) : streamDecrypt(key, fin, fout);

  long dsec=(System.currentTimeMillis()-start+50)/100;
  if (dsec!=0) System.out.println((dsec/10)+" sec, "+(cnt*10/dsec)+" b/s");

  fout.close();
  fin.close();
 }

 /**
  * Prints the error message and exits.
  */
 public static void invalidArgs()
 {
  System.err.println("Invalid args. Must be:");
  System.err.println("e|d key_file input_file output_file");
  System.exit(1);
 }

 /**
  * Reads file with passed <code>name</code>.
  *
  * @param name file name
  * @return file content
  * @throws Exception in case of errors
  */
 public static byte[] readFile(String name) throws Exception
 {
  RandomAccessFile raf=new RandomAccessFile(name, "r");

  byte[] ret=new byte[(int)raf.length()];
  raf.readFully(ret);

  raf.close();
  return ret;
 }
}

  1. Отправляем на вход blockEncrypt() блоки длиной [minLen, minLen*2[. Фактически, все блоки кроме последнего будут иметь длину minLen в силу чего количество перестановок, создаваемых функцией createPermutation(), будет невелико, что позволяет эффективно кэшировать уже созданные перестановки не вычисляя их каждый раз заново.

    Обратите внимание: параметр len функции createPermutation() -- это количество остатков, а не длина блока. Т.е. блоки одинаковой длины, вообще говоря, могут порождать разное количество остатков.

  2. Предыдущий зашифрованный блок (prevEncr) передается в blockEncrypt() последним аргументом. В результате чего, один и тот же блок открытого текста будет порождать, как правило, различные блоки зашифрованного текста, что положительно сказывается на криптостойкости.
  3. Формат записываемого блока тривиален: 2 байта длина блока, затем сам блок. Все числа записываются в формате big-endian, т.е. старший байт первым.
  4. Ошибка: заголовок блока содержит некорректную длину.

    Длина зашифрованного блока, очевидно, лежит в пределах ]minLen, minLen*3[. На самом деле, максимально возможное ее значение лишь ненамного превышает minLen*2, но формула для вычисления точной границы достаточно громоздка и, к тому же, ее использование ничего не улучшит по сути.

  5. Ошибка: прочитано байт меньше, чем указано в заголовке.
  6. Интерпретируем байты ключа key как положительное число B2 в формате big-endian. Обратите внимание: нулевые байты в начале массива key никак не влияют на значение B2.
  7. Непосредственно перед шифрованием вызовом appendHash(plain, hash) к числу A1 добавляется хэш, т.е. число A'1 получается из A1 путем дописывания хэша, рассчитанного по A1.
  8. Преобразовываем число A'2 (результат шифрования A'1) в массив байт encr и отбрасываем начальные нули.
  9. Ошибка: хэш значения дешифрованных блоков (с заменой значения старшего значащего остатка и без) совпадают, т.е. во время дешифрования функция blockDecrypt() не смогла бы определить какой из вариантов дешифрованого текста является правильным. Как следствие, шифрование данного текста с использованием данного ключа запрещено.

    На первый взгляд может показаться, что невозможность шифрования произвольного текста на произвольном ключе является фатальным недостатком алгоритма. Тем не менее, вероятность наступления данного события пренебрежительно мала: должен существовать нулевой остаток, он должен попасть на нужное место и хэш значения должны совпасть. Т.е. вероятность сопоставима с вероятностью угадать ключ "методом тыка", возведенной в квадрат.

    В предыдущей версии алгоритма для сохранения информации о замене значения старшего значащего остатка использовался дополнительный бит -- старший значащий (msb). Это позволяло шифровать любой текст, но приводило к проблемам. Так, например, если msb уже был равен 1 (вероятность порядка 1/16), то к числу дописывался старший байт со значением 0x80, что заметно искажало статистические характеристики зашифрованного текста.

  10. Сначала пробуем расшифровать без замены старшего значащего остатка.
  11. Вторая попытка: пробуем расшифровать с заменой.
  12. Ошибка: несовпадение хэша, добавленного к блоку открытого текста перед шифрованием, с хэшем, рассчитанным по самому блоку. Причина: неверный ключ и/или текст для дешифрования.
  13. При несовпадении хэша результат дешифрования пользователю не возвращается. Такой подход позволяет достаточно надежно отслеживать некорректность переданного ключа и/или зашифрованных данных, а также предотвращает некоторые виды атак.
  14. null значение свидетельствует о том, что функция basicDecrypt() была вызвана с заменой старшего значащего остатка, но его значение оказалось отличным от 1.
  15. После отбрасывания начальных нулей первый байт массива decr будет первым байтом дописанного в blockEncrypt() хэша, чье значение гарантированно отличается от нуля.
  16. Изменяем значение наибольшего значащего остатка с 0 на 1. Дело в том, что нулевые "цифры" в начале числа не влияют на его значение и при вызове функции computeNumber() будут потеряны, если не принять специальных мер.
  17. Выполняем обратную замену, если она возможна.
  18. Минимальная длина берется кратной длине ключа и вычисляется таким образом, чтобы количество остатков от деления на ключ порождало количество перестановок примерно соответствующее 2keyLength.
  19. Ошибка: в начале ключа находится один или несколько нулевых байт.

    В силу того, что нули в начале числа не имеют значения, реальная длина ключа (т.е. позиция старшего ненулевого бита) оказывается существенно меньше длины переданного массива байт. Если переданное значение ключа действительно нужно использовать, то начальные нули необходимо удалить, например с помощью stripLeadingZeros().

  20. Ошибка: четное значение ключа.

    Четные значения ключа использовать не рекомендуется в силу того, что B1 и B2 должны быть взаимно простыми числами, а в нашем случае B1 -- это 2, а B2 равно значению ключа.

    Нетрудно видеть, что требование взаимной простоты является одним из ключевых условий стойкости криптоалгоритма. Так, например, если в качестве ключа взять 256==28, то вся работа алгоритма сведется к простой перестановке байт.

  21. Ошибка: длина текста для шифрования меньше минимально допустимой длины.

    Безусловно, ограничение на минимальную длину открытого текста не очень удобно на практике. Тем не менее, криптостойкость алгоритма существенным образом зависит от количества переставляемых в basicEncrypt() остатков (например, если количество остатков равно 1, то возвращаемое значение A2 будет равно переданному A1, т.е. никакого шифрования не получится вообще).

    Наиболее очевидным решением проблемы недостаточной длины открытого текста является его "разбавление" случайными байтами до нужной длины непосредственно перед шифрованием и отбрасывание добавленных байт после дешифрования. Тем не менее, я не стал встраивать эту функциональность в текущую версию DersCrypt, т.к. не вполне определился с деталями возможной реализации в силу того, что некоторые частные случаи ее применения не должны снижать общую криптостойкость алгоритма.

  22. Вычисление остатков от деления на b производится простым последовательным делением. Более эффективным является деление a на две примерно равные части (делим на b2n для некоторого n) и рекурсивного применения той же процедуры к оставшимся частям.
  23. Следует отметить, что функция computeHash() не должна применяться для получения хэш значений в случае заранее известного ключа. Дело в том, что зная ключ можно без особого труда построить массив байт нужной длины, чье хэш значение совпадет с заданным. Все, что нужно -- это создать массив байт, биты которого (выбираемые extractBits()) имеют заданные значения и применить к нему basicDecrypt().
  24. Параметр prevData существенным образом влияет на результат работы computeHash(). Поэтому в случае его отсутствия делается попытка создания более-менее случайного набора байт по значению ключа.

    Создаваемое значение prevHash должно существенно изменяться при изменении ключа, а сам ключ должно быть невозможно по нему вычислить. Выбранный подход заключается в перестановке бит числа с равномерно распределенными нулями и единицами (0x55 равно 01010101).

    Вероятно, алгоритм создания prevHash может быть улучшен.

  25. Первый байт массива hash должен всегда отличаться от нуля, т.к. нулевые байты в начале числа не влияют на его значение и после дешифрования будут потеряны, если не принять специальных мер.

    Выбор 1 в качестве замены для нуля достаточно произволен -- другие значения могут оказаться более удачными. Я исходил из того, что если уж и приписывать к неизвестному (криптоаналитику) набору бит фиксированные биты, то их количество должно быть наименьшим.

  26. Массив hash разрезается на две половины таким образом, что при нечетном количестве байт большая половина будет расположена слева.
  27. Биты выбираются следующим образом. Все биты массива data делятся на bitsLen*8+1 отрезков. Позиция nj последовательно попадает на их границы. Например n0==0, а nbitsLen*8+1==data.length*8-1, т.е. это первый и последний бит data. Т.к. значение j изменяется в пределах [1, data.length*8], то первый и последний бит никогда не выбираются.
  28. Перестановка создается исходя из следующих критериев:

    1. Все элементы разделяются на две половины, правая половина меняется положением с левой:
      "Нулевая" перестановка:  0 1 2 3 4
      После разделения:  3 4 0 1 2
    2. Элементы перемешиваются каждый на своей половине таким образом, что ни одна из пар не сохраняется. Т.е. в итоговой перестановке 4 не может следовать за 3, 1 -- за 0 и т.д.

    Таким образом, все элементы (кроме среднего для нечетного количества элементов) гарантированно меняют свои места, а также изменяется их положение друг относительно друга.

    Как можно видеть, количество возможных перестановок меньше чем n!. Например, существует единственная перестановка из четырех элементов, удовлетворяющая приведенным выше условиям: (3,2,1,0), т.е. все элементы выстроены в обратном порядке.

  29. Разделяем элементы на две половины заполняя массив val.
  30. Константа -2 означает, что позиция еще не назначена. Привычное -1 не подходит, т.к. 0-1 также равно -1, т.е. с размещением нулевой позиции возникнут трудности.
  31. Выполняем два прохода: для левой и правой половины.
  32. Комментарий говорит о том, что нужно предотвратить ситуацию, когда все элементы кроме последнего заняли позиции таким образом, что единственное оставшееся место следует сразу же за предпоследним.
  33. Найдены две последовательные незаполненные позиции. Единственный возможный вариант: разместить последний элемент в первой, а предпоследний -- во второй.
  34. Делимое b2 стало меньше делителя div -- имеет смысл снова начать с b для большего разнообразия остатков.
  35. Переменная sub становится равной 1, если не занята следующая за только что присвоенной позиция, т.е. очередной элемент не должен в нее попасть (т.к. образуется последовательная пара) и, следовательно, количество оставшихся мест для следующей итерации нужно уменьшить на единицу.
  36. Вызов check() является одним из ключевых условий работы криптоалгоритма. Фактически, все функции xxxEncrypt() и xxxDecrypt() полагаются на то, что переданные аргументы удовлетворяют проверяемым функцией check() условиям.

    Тем не менее, вызов check() не встраивался непосредственно в тело xxxEncrypt() и xxxDecrypt(), т.к. представленная эталонная реализация создана для практического исследования свойств криптоалгоритма. В частности, для исследования его поведения при получении параметров, выходящих за рамки предусмотренных значений.

Реализации для использования

В данном разделе представлены реализации, предназначенные для практического использования. Об их сравнительной производительности можно судить по следующей таблице, в которой приведена скорость шифрования в килобайтах в секунду на 256-битном ключе для двух компьютеров разной архитектуры:

Эталонная
реализация
Java
реализация
C++ реализация
универсальная
C++ реализация
оптимизированная
Pentium 4 52.5 K/s 74.2 K/s 351.8 K/s 612.7 K/s
Athlon 86.4 K/s 127.2 K/s 1149.2 K/s 1404.6 K/s

Как можно видеть, оптимизированная C++ реализация в 8-11 раз быстрее Java реализации, которая, в свою очередь, на 40-50 процентов быстрее эталонной. Судя по всему, неприемлемой производительностью Java реализации обязаны стандартному классу java.math.BigInteger, чей код никак нельзя признать оптимальным.

Java реализация

Данная реализация так же написана на Java, но в отличие от эталонной реализации предназначена для непосредственного использования и включения во внешние проекты.

Реализация:  derscrypt.jar
Исходный код:  src.zip

Для шифрования файла plain_file с использованием ключа key_file:
java -jar derscrypt.jar e key_file plain_file encr_file
Результат будет помещен в encr_file.

Для дешифрования файла encr_file с использованием ключа key_file:
java -jar derscrypt.jar d key_file encr_file decr_file
Результат будет помещен в decr_file и должен полностью совпадать с исходным файлом plain_file.

C++ реализация

Данная реализация написана на C++ и предназначена для непосредственного использования. После внесения необходимых изменений может включаться во внешние проекты.

Реализация,
Windows
универсальная:  derscrypt-i386.zip
оптимизированная для Pentium 4:  derscrypt-pentium4.zip
оптимизированная для Athlon:  derscrypt-athlon.zip
Исходный код:  src.zip

Для шифрования файла plain_file с использованием ключа key_file:
derscrypt e key_file plain_file encr_file
Результат будет помещен в encr_file.

Для дешифрования файла encr_file с использованием ключа key_file:
derscrypt d key_file encr_file decr_file
Результат будет помещен в decr_file и должен полностью совпадать с исходным файлом plain_file.

Ретроспектива

Первое сообщение о DersCrypt

Впервые криптоалгоритм был представлен в феврале 2004 года в виде сообщения в профильные ньюсгруппы UseNet (текст сообщения). Наиболее ценное обсуждение произошло в конференции fido7.ru.crypt сети FidoNet, или просто ФИДО.

Фактически, и на сегодняшний день конференция RU.CRYPT является наилучшим местом для обсуждения DersCrypt и связанных с ним криптографических вопросов.

DersCrypt v1.0

В апреле 2005 года увидела свет первая версия DersCrypt, заметно отличавшаяся от того, что было представлено в самом начале. Она была опубликована в виде отдельной страницы на сайте ders.stml.net/crypt, посвященной криптографии (текст первой версии).

Ключевым источником информации для ее создания безусловно являлась дискуссия с участием специалистов из RU.CRYPT, которым я чрезвычайно признателен. В виду отсутствия явных ошибок, никакого обсуждения версии 1.0 в конференции RU.CRYPT не было.

Тем не менее, ссылки на DersCrypt разошлись по Рунету и дискуссия продолжилась в рамках другой аудитории. На текущий момент можно констатировать, что кроме предложений по отказу от использования msb никаких принципиальных недостатков выявлено не было.

Текущая версия DersCrypt v1.1 предлагает решение проблемы msb и представляет улучшенное описание алгоритма.

Заключение

Как можно видеть, DersCrypt вступил в пору зрелости. Принципиальная новизна алгоритма полностью себя оправдала. Судя по всему, шифрование с использованием систем счисления имеет право на жизнь.

Тем не менее, мне ничего не известно о действительно серьезных исследованиях DersCrypt в рамках специализированных институтов и структур. Как следствие, в течение нескольких ближайших лет алгоритм не может быть рекомендован к использованию в критически важных для безопасности целях. "Домашнее использование" безусловно оправдано.

 
14.03.2006
Версия для печати Версия для печати Запомнить ссылку Запомнить ссылку
Ваша оценка:  1   2   3   4   5     

 О проектеПерепечаткаАвторамПартнерыО нас пишут
Наверх
©2003—2007. GETINFO.RU. ВСЕ ПРАВА ЗАЩИЩЕНЫ.