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(24209)
Криптография: зачем это нужно(10099)
Почему криптосистемы ненадежны?(9867)
Криптографический алгоритм DersCrypt(4438)
Криптографический алгоритм DersCrypt (версия 1.0)(4209)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Криптография » Криптографический алгоритм DersCrypt (версия 1.0)

Криптографический алгоритм DersCrypt (версия 1.0)


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

Введение

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

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

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

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

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

Рассмотрим следующий пример. Путь нам необходимо зашифровать текст из четырех букв: 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 сам по себе непригоден к практическому применению в силу того, что имея и открытый текст и результат его шифрования крайне легко вычислить использованный для шифрования ключ B2. Max Alekseyev указал на то, что имея число A1 в системе счисления по основанию B2 и число A2, полученное из A1 произвольной перестановкой цифр, разность A1-A2 всегда делится на B2-1. Например, нетрудно видеть, что 1633837924-3297413368=-1663575444 делится на 9. Поэтому результат шифрования не должен являться простой перестановкой цифр исходного числа.

Таким образом, непосредственно перед разложением числа A1 на остатки от деления на B2 и их перестановкой, его нужно изменить, превратив в число A'1. При этом, разность A1-A'2 на B2-1, вообще говоря, делиться не будет.

Наиболее простым и очевидным решением является получение числа A'1 из A1 путем приписывания к A1 некоторого количества случайных байт: слева и справа. После дешифрования, приписанные байты достаточно просто отбросить, получив исходное число A1.

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

Представленная ниже реализация 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.

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

Ниже приводится исходный код с пронумерованными комментариями.
import java.io.DataInput;
import java.io.DataOutput;
import java.io.DataOutputStream;
import java.io.FileOutputStream;
import java.io.RandomAccessFile;
import java.math.BigInteger;
import java.util.LinkedList;

/**
 * This is the reference implementation of DersCrypt crypto algorithm.
 *
 * @see <a href="http://ders.angen.net/crypt/derscrypt/derscrypt.html">Crypto
 * algorithm DersCrypt</a> -- the DersCrypt home page.
 */

public final class DersCrypt
{
 /**
  * Encrypts <code>din</code> and writes the result to <code>dout</code>.
  *
  * @param key key to use
  * @param din stream to read plain text from
  * @param length number of bytes to read from <code>din</code>
  * @param dout stream to write encrypted text to
  * @throws Exception in a case of errors
  */
 public static void streamEncrypt(byte[] key, DataInput din, int length,
   DataOutput dout) throws Exception
 {
  int req=requiredLength(key.length);
  byte[] prevEncr=null;
  for (int left=length, len; left>0; left-=len) {
      len= (left<req*2) ? left : req;  // [1] [2]

      byte[] plain=new byte[len];
      din.readFully(plain);

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

      dout.writeChar(encr.length);  // [4]
      dout.write(encr);
  }
 }

 /**
  * Decrypts <code>din</code> and writes the result to <code>dout</code>.
  *
  * @param key key to use
  * @param din stream to read encrypted text from
  * @param length number of bytes to read from <code>din</code>
  * @param dout stream to write decrypted text to
  * @throws Exception in a case of errors
  */
 public static void streamDecrypt(byte[] key, DataInput din, int length,
   DataOutput dout) throws Exception
 {
  String errMsg="Invalid data: Invalid block format";

  int req=requiredLength(key.length);
  byte[] prevEncr=null;
  for (int done=0; done<length; ) {
      if (length-done<2+req) throw new Exception(errMsg);  // [5]

      int len=din.readChar();
      done+=2;

      if (len<req || len>length-done) throw new Exception(errMsg);  // [6]

      byte[] encr=new byte[len];
      din.readFully(encr);
      done+=len;

      byte[] decr=blockDecrypt(key, encr, prevEncr);
      prevEncr=encr;  // changed msb doesn't matter  // [7]
      
      if (decr==null) throw new Exception("Invalid data: Hash mismatch");  // [8]
      dout.write(decr);
  }
 }

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

  byte[] hash=computeHash(key.length, b2, plain, prevEncr);
  if (hash[0]==0) hash[0]=1;  // [10]

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

  boolean[] flagMsb=new boolean[2];
  BigInteger aPr2=basicEncrypt(b2, aPr1, flagMsb);
  byte[] encr=stripLeadingZeros(aPr2.toByteArray());  // [12]

  boolean msb= (flagMsb[0]) ? flagMsb[1] : xorAllBits(hash);  // [13]
  return setMsb(encr, msb);  // [14]
 }

 /**
  * Decrypts a block of encrypted text.
  * Note that current implementation modifies <code>encr</code> parameter (the
  * most significant bit gets cleared).
  *
  * @param key key to use
  * @param encr encrypted text to decrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @return decrypted text or <code>null</code> in a case of hash mismatch [15]
  */
 public static byte[] blockDecrypt(byte[] key, byte[] encr, byte[] prevEncr)
 {
  boolean msb=clearMsb(encr);  // modifies encr!!! [16]
  BigInteger aPr2=new BigInteger(1, encr), b2=new BigInteger(1, key);
  BigInteger aPr1=basicDecrypt(b2, aPr2, msb);
  byte[] decr=stripLeadingZeros(aPr1.toByteArray());  // [17]
  
  byte[][] ph=extractHash(decr, key.length);
  byte[] plain=ph[0], hash=ph[1];

  byte[] hash2=computeHash(key.length, b2, plain, prevEncr);
  if (hash[0]!=hash2[0] && !(hash[0]==1 && hash2[0]==0)) return null;  // [18]

  for (int i=1; i<key.length; i++)
      if (hash[i]!=hash2[i]) return null;

  return plain;
 }

 /**
  * Computes hash of a block of data. [19]
  *
  * @param len length of a hash to compute
  * @param b2 key value to use
  * @param data data 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;  // [20]
  }
  byte[] prevHash=permuteBits(bits, b2);

  BigInteger a1=new BigInteger(1, appendHash(data, prevHash));
  BigInteger a2=basicEncrypt(b2, a1, new boolean[2]);
  byte[] encr=stripLeadingZeros(a2.toByteArray());
  return permuteBits(extractBits(encr, len), b2);
 }
 
 /**
  * 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++)
      ;

  byte[] ret=new byte[bytes.length-i];
  System.arraycopy(bytes, i, ret, 0, ret.length);

  return ret;
 }
 
 /**
  * Extracts bits from <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);  // [21]
          if ((data[n/8]&BIT_MASKS[n%8])!=0)
             ret[i]|=mask;
      }
  }

  return ret;
 }
 
 /**
  * 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 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);  // [22]
  System.arraycopy(data, 0, ret, len-mid, data.length);
  System.arraycopy(hash, len-mid, ret, len-mid+data.length, mid);

  return ret;
 }

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

  System.arraycopy(bytes, 0, hash, 0, hashLen-mid);
  System.arraycopy(bytes, hashLen-mid, data, 0, data.length);
  System.arraycopy(bytes, hashLen-mid+data.length, hash, hashLen-mid, mid);

  return new byte[][]{data, hash};
 }
 
 /**
  * Xors all bits of <code>data</code>.
  *
  * @param data array to process
  * @return <code>true</code> if resulting bit is non-zero
  */
 public static boolean xorAllBits(byte[] data)
 {
  int a=data[0];
  for (int i=1; i<data.length; i++) a^=data[i];

  a=(a>>4)^(a&0xf);
  a=(a>>2)^(a&0x3);
  a=(a>>1)^(a&0x1);

  return (a&0x1)!=0;
 }

 /**
  * Sets most significant bit of <code>data</code> to <code>msb</code> value. 
  *
  * @param data data to change
  * @param msb value to set
  * @return changed data
  */
 public static byte[] setMsb(byte[] data, boolean msb)
 {
  if ((data[0]&0x80)!=0) {  // [23]
     byte[] tmp=new byte[data.length+1];
     System.arraycopy(data, 0, tmp, 1, data.length);

     data=tmp;
  }

  if (msb) data[0]|=0x80;
  return data;
 }

 /**
  * Clears most significant bit of <code>data</code>. 
  *
  * @param data data to change
  * @return original msb value
  */
 public static boolean clearMsb(byte[] data)
 {
  boolean ret= (data[0]&0x80)!=0;
  data[0]&=0x7f;

  return ret;
 }

 /**
  * Basic encryption functionality.
  *
  * @param b2 key value to use
  * @param a1 number to encrypt
  * @param flagMsb boolean flag and msb (most significant bit) value output
  *        parameters combined in one array 
  * @return encrypted number
  */
 public static BigInteger basicEncrypt(BigInteger b2, BigInteger a1,
   boolean[] flagMsb)
 {
  BigInteger[] rems=computeRemainders(a1, b2);
  BigInteger[] rems2=permute(rems, b2, false);

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

  BigInteger a2=computeNumber(rems2, b2);
  return a2;
 }

 /**
  * Basic decryption functionality.
  *
  * @param b2 key value to use
  * @param a2 number to decrypt. Note that msb must be cleared at this point.
  * @param msb msb value that was cleared
  * @return decrypted number
  */
 public static BigInteger basicDecrypt(BigInteger b2, BigInteger a2,
   boolean msb)
 {
  BigInteger[] rems=computeRemainders(a2, b2);

  if (rems[0].equals(BigInteger.ONE) && msb)  // [25]
     rems[0]=BigInteger.ZERO;

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

 /**
  * 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)) {  // [26]
        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++) {  // [27]
      a=a.multiply(b);
      a=a.add(rems[i]);
  }

  return a;
 }

 /**
  * Creates a permutation of passed length. [28]
  *
  * @param len length of permutation
  * @param b number to create permutation from
  * @param inverse <code>true</code> if inverse permutation must be created
  * @return array of positions
  */
 public static int[] createPermutation(int len, BigInteger b, boolean inverse)
 {
  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=new BigInteger(""+(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;
              }
          }
      }
  }

  if (inverse) {
     int[] ret2=new int[len];
     for (int i=0; i<len; i++) ret2[ret[i]]=i;

     return ret2;
  }

  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, inverse);
  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 in
  * @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, false);

  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;
 }

 /**
  * Returns minimal data length required for passed key length. [36]
  *
  * @param keyLength key length
  * @return minimal required data length
  */
 public static int requiredLength(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 length to check
  * @throws Exception in a case of errors
  */
 public static void check(byte[] key, int length) throws Exception
 {
  if (key[0]==0)
     throw new Exception("Suspectable key: Leading zeros are useless");  // [37]

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

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

 /** array of masks to extract successive bits of a byte from left to right */
 public static final int[] BIT_MASKS=new int[]{
   0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
 };
 
 /**
  * Prints 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 a 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;
 }

 /**
  * 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);

  RandomAccessFile din=new RandomAccessFile(sIn, "r");
  int length=(int)din.length();
  check(key, length);  // [40]

  DataOutputStream dout=new DataOutputStream(new FileOutputStream(sOut));

  long start=System.currentTimeMillis();

  if      ("e".equals(sCmd)) streamEncrypt(key, din, length, dout);
  else if ("d".equals(sCmd)) streamDecrypt(key, din, length, dout);

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

  din.close();
  dout.close();
 }
}

  1. Шифруемый блок должен быть не короче req. Очевидно, что весь поток данных (длины length) можно разбить на блоки длины [req, req*2[.

    На текущий момент была выбрана простейшая схема, в которой все блоки кроме последнего имеют одну и ту же длину -- req. Польза такого выбора в том, что количество перестановок, создаваемых createPermutation(), будет невелико, что позволит эффективно кэшировать уже созданные перестановки не вычисляя их каждый раз заново.

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

  2. В принципе, для реализации выбранной схемы разбиения потока din на блоки параметр length не требуется: реализация может пытаться считывать блоки длины req*2 и передавать в blockEncrypt() их половины плюс последний блок неполной длины, требующий особой обработки. Тем не менее, я выбрал интерфейс с явным указанием длины, т.к. в противном случае алгоритм разбиения становится достаточно громоздким ничего не улучшая по сути.

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

  3. Предыдущий зашифрованный блок (prevEncr) передается в blockEncrypt() последним аргументом. В результате чего, один и тот же блок открытого текста будет порождать, как правило, различные блоки зашифрованного текста, что положительно сказывается на криптостойкости.
  4. Формат записываемого блока тривиален: 2 байта длина блока, затем сам блок. Все числа записываются в формате big-endian, т.е. старший байт первым.
  5. Ошибка: в потоке осталось байт меньше, чем минимально допустимая длина блока плюс 2 байта на длину.
  6. Ошибка: заголовок блока содержит некорректную длину.
  7. Комментарий говорит о том, что хоть вызов blockDecrypt() и изменяет значение encr, это изменение не имеет значения для computeHash(). Дело в том, что изменяется только наибольший значащий бит (msb), а extractBits() никогда не выбирает крайние биты.
  8. Ошибка: null значение свидетельствует о несовпадении хэша, добавленного к блоку открытого текста перед шифрованием, с хэшем, рассчитанным по самому блоку. Причина: неверный текст для дешифрования и/или неверный ключ.
  9. Интерпретируем байты ключа key как положительное число B2 в формате big-endian. Обратите внимание: нулевые байты в начале массива key никак не влияют на значение B2.
  10. Первый байт массива hash должен всегда отличаться от нуля, т.к. нулевые байты в начале числа не влияют на его значение и после дешифрования будут потеряны, если не принять специальных мер.

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

  11. Непосредственно перед шифрованием вызовом appendHash(plain, hash) к числу A1 добавляется хэш, т.е. число A'1 получается из A1 путем дописывания хэша, рассчитанного по A1.
  12. Преобразовываем число A'2 (результат шифрования A'1) в массив байт encr и отбрасываем начальные нули.
  13. Еще одно место, необходимое для сохранения нулей в начале числа: дело в том, что нулевым может оказаться и старший остаток от деления на B2.

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

    Я выбрал второй путь: если старший значащий остаток равен 1, то наибольший значащий бит (msb) зашифрованного текста свидетельствует о том, должен ли он быть обнулен (msb==1) перед дешифрованием. В любом случае, сам msb перед дешифрованием должен обнуляться, т.к. он всегда приписывается к результату шифрования, а не является частью числа A'2.

    Если же старший значащий остаток не равен 1, то значение msb игнорируется и, следовательно, должно быть случайным. Для получения псевдослучайного бита используется вызов xorAllBits(hash).

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

  14. Дописываем значение msb к зашифрованному тексту, т.е. результатом работы blockEncrypt() является число A'2 с дописанным наибольшим значащим битом.
  15. При несовпадении хэша результат дешифрования пользователю не возвращается. Такой подход позволяет достаточно надежно отслеживать некорректность переданного ключа и/или зашифрованных данных, а также предотвращает некоторые виды атак.

    Например, существует очевидная атака на базовый алгоритм шифрования/дешифрования: если на вход алгоритма подать два числа, отличающиеся только значением младшего значащего бита, то разность полученных после шифрования/дешифрования чисел будет равна B2n (для некоторого n). Т.е. если бы в случае несовпадения хэша blockDecrypt() возвращала бы массив decr, описанная выше атака была бы возможна и против DersCrypt.

  16. Комментарий обращает внимание на то, что blockDecrypt() изменяет значение одного из своих параметров, что, вообще говоря, неправильно с точки зрения концептуальной чистоты интерфейса. Тем не менее, это изменение не вызывает проблем в текущей реализации DersCrypt, так что я посчитал неоправданным создание копии массива encr для предотвращения побочных эффектов.
  17. После отбрасывания начальных нулей, первый байт массива decr будет первым байтом дописанного в blockEncrypt() хэша, чье значение гарантированно отличается от нуля.
  18. Учитываем, что нулевой байт хэша мог быть изменен.
  19. Следует отметить, что функция computeHash() не должна применяться для получения хэш значений в случае заранее известного ключа. Дело в том, что зная ключ можно без особого труда построить массив байт нужной длины, чье хэш значение совпадет с заданным. Все, что нужно -- это создать массив байт, биты которого (выбираемые extractBits()) имеют заданные значения и применить к нему basicDecrypt().
  20. Параметр prevData существенным образом влияет на результат работы computeHash(). Поэтому в случае его отсутствия делается попытка создания более-менее случайного набора байт по значению ключа.

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

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

  21. Биты выбираются следующим образом. Все биты массива data делятся на bitsLen*8+1 отрезков. Позиция nj последовательно попадает на их границы. Например n0==0, а nbitsLen*8+1==data.length*8-1, т.е. это первый и последний бит data. Т.к. значение j изменяется в пределах [1, data.length*8], то первый и последний бит никогда не выбираются.
  22. Массив hash разрезается на две половины таким образом, что при нечетном количестве байт большая половина будет расположена слева.
  23. Расширяем массив data, т.к. старший бит уже равен 1.
  24. Вычисляем значение flagMsb в зависимости от значения старшего остатка.
  25. Учитываем значение msb.
  26. Вычисление остатков от деления на b производится простым последовательным делением. Более эффективным является деление a на две примерно равные части (делим на bn для некоторого n) и рекурсивного применения той же процедуры к оставшимся частям.
  27. Аналогично, прирост производительности можно получить отказавшись от последовательного умножения на b.
  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. Минимальная длина берется кратной длине ключа и вычисляется таким образом, чтобы количество остатков от деления на ключ порождало количество перестановок примерно соответствующее 2длина ключа.
  37. Ошибка: в начале ключа находится один или несколько нулевых байт.

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

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

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

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

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

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

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

  40. Вызов check() является одним из ключевых условий работы криптоалгоритма. Фактически, все функции xxxEncrypt() и xxxDecrypt() полагаются на то, что переданные аргументы удовлетворяют проверяемым функцией check() условиям.

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

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

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

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

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

Заключение

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

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

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

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