DersCrypt обладает следующими достоинствами:
Рассмотрим следующий пример. Путь нам необходимо зашифровать текст из четырех букв: 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 состоит из следующих шагов:
A1 в некоторой системе счисления S1 по основанию B1.
A1 переводится в другую систему счисления S2 по основанию B2. Число B2 является ключом.
A1 в системе счисления S2 переставляются, в результате чего получается число A2. Перестановка задается значением ключа.
A2 переводится в исходную систему счисления S1.
A2 в системе счисления S1 и является результатом шифрования.
0x61, 0x62, 0x63, 0x64, соответствующая строке "abcd". Число A1 -- это 0x61626364 в шестнадцатеричной системе счисления, т.е. B1=16.
A1 в десятичной системе счисления (т.е. B2=10) -- это 1633837924.
(5,8,7,6,9,0,3,2,1,4) к цифрам 1,6,3,3,8,3,7,9,2,4 получим число A2=3297413368.
A2 в шестнадцатеричной системе счисления -- это 0xC48A88F8.
0xC4, 0x8A, 0x88, 0xF8.
B2n для некоторого n. Применительно к нашему примеру: A1=1633837924, A'1=1633837925 и A2=3297413368, A'2=3297513368. Как можно видеть, A2-A'2=-100000, т.е. 105.
A1 в системе счисления по основанию B2 и число A2, полученное из A1 произвольной перестановкой цифр, разность A1-A2 всегда делится на B2-1. Например, нетрудно видеть, что 1633837924-3297413368=-1663575444 делится на 9.
A1 превращается в некоторое число A'1 посредством приписывания к A1 некоторого количества случайных байт слева и справа. После дешифрования приписанные байты достаточно просто отбросить, получив исходное число A1.
В силу того, что действительно случайные байты довольно сложно получить на практике, в DersCrypt используется предварительное шифрование числа A1 базовым алгоритмом и извлечение из полученного числа A2 последовательности бит нужной длины. На самом деле, для учета значения предыдущего зашифрованного блока текста, процедура формирования псевдослучайной битовой последовательности чуть более усложнена. Ознакомиться с ней можно непосредственно по коду эталонной реализации, комментарии к которой являются неотъемлемой частью описания алгоритма.
Для наибольшего удобства неискушенных в программировании пользователей, использующих разнообразные платформы, языком реализации выбрана Java, а исходный код оформлен исходя из упрощения понимания, а не производительности и/или простоты включения во внешние проекты. Для реального использования предназначены реализации, следующие далее.
javac DersCrypt.javaDersCrypt.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.
0x00. Не следует путать нулевой байт с символом '0', чье значение 0x30 вполне подходит.
Для упрощения создания ключа мной была написана утилита KeyGen.java. Ее компиляция и запуск выполняются следующими командами:
javac KeyGen.java
java KeyGen key_file
после чего KeyGen запросит длину ключа в битах, максимальное значение, а также серию значений для генерации ключа. Например:
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!
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;
}
}
|
blockEncrypt() блоки длиной [minLen, minLen*2[. Фактически, все блоки кроме последнего будут иметь длину minLen в силу чего количество перестановок, создаваемых функцией createPermutation(), будет невелико, что позволяет эффективно кэшировать уже созданные перестановки не вычисляя их каждый раз заново.
Обратите внимание: параметр len функции createPermutation() -- это количество остатков, а не длина блока. Т.е. блоки одинаковой длины, вообще говоря, могут порождать разное количество остатков.
prevEncr) передается в blockEncrypt() последним аргументом. В результате чего, один и тот же блок открытого текста будет порождать, как правило, различные блоки зашифрованного текста, что положительно сказывается на криптостойкости.
Длина зашифрованного блока, очевидно, лежит в пределах ]minLen, minLen*3[. На самом деле, максимально возможное ее значение лишь ненамного превышает minLen*2, но формула для вычисления точной границы достаточно громоздка и, к тому же, ее использование ничего не улучшит по сути.
key как положительное число B2 в формате big-endian. Обратите внимание: нулевые байты в начале массива key никак не влияют на значение B2.
appendHash(plain, hash) к числу A1 добавляется хэш, т.е. число A'1 получается из A1 путем дописывания хэша, рассчитанного по A1.
A'2 (результат шифрования A'1) в массив байт encr и отбрасываем начальные нули.
blockDecrypt() не смогла бы определить какой из вариантов дешифрованого текста является правильным. Как следствие, шифрование данного текста с использованием данного ключа запрещено.
На первый взгляд может показаться, что невозможность шифрования произвольного текста на произвольном ключе является фатальным недостатком алгоритма. Тем не менее, вероятность наступления данного события пренебрежительно мала: должен существовать нулевой остаток, он должен попасть на нужное место и хэш значения должны совпасть. Т.е. вероятность сопоставима с вероятностью угадать ключ "методом тыка", возведенной в квадрат.
В предыдущей версии алгоритма для сохранения информации о замене значения старшего значащего остатка использовался дополнительный бит -- старший значащий (msb). Это позволяло шифровать любой текст, но приводило к проблемам. Так, например, если msb уже был равен 1 (вероятность порядка 1/16), то к числу дописывался старший байт со значением 0x80, что заметно искажало статистические характеристики зашифрованного текста.
null значение свидетельствует о том, что функция basicDecrypt() была вызвана с заменой старшего значащего остатка, но его значение оказалось отличным от 1.
decr будет первым байтом дописанного в blockEncrypt() хэша, чье значение гарантированно отличается от нуля.
0 на 1. Дело в том, что нулевые "цифры" в начале числа не влияют на его значение и при вызове функции computeNumber() будут потеряны, если не принять специальных мер.
2keyLength.
В силу того, что нули в начале числа не имеют значения, реальная длина ключа (т.е. позиция старшего ненулевого бита) оказывается существенно меньше длины переданного массива байт. Если переданное значение ключа действительно нужно использовать, то начальные нули необходимо удалить, например с помощью stripLeadingZeros().
Четные значения ключа использовать не рекомендуется в силу того, что B1 и B2 должны быть взаимно простыми числами, а в нашем случае B1 -- это 2, а B2 равно значению ключа.
Нетрудно видеть, что требование взаимной простоты является одним из ключевых условий стойкости криптоалгоритма. Так, например, если в качестве ключа взять 256==28, то вся работа алгоритма сведется к простой перестановке байт.
Безусловно, ограничение на минимальную длину открытого текста не очень удобно на практике. Тем не менее, криптостойкость алгоритма существенным образом зависит от количества переставляемых в basicEncrypt() остатков (например, если количество остатков равно 1, то возвращаемое значение A2 будет равно переданному A1, т.е. никакого шифрования не получится вообще).
Наиболее очевидным решением проблемы недостаточной длины открытого текста является его "разбавление" случайными байтами до нужной длины непосредственно перед шифрованием и отбрасывание добавленных байт после дешифрования. Тем не менее, я не стал встраивать эту функциональность в текущую версию DersCrypt, т.к. не вполне определился с деталями возможной реализации в силу того, что некоторые частные случаи ее применения не должны снижать общую криптостойкость алгоритма.
b производится простым последовательным делением. Более эффективным является деление a на две примерно равные части (делим на b2n для некоторого n) и рекурсивного применения той же процедуры к оставшимся частям.
computeHash() не должна применяться для получения хэш значений в случае заранее известного ключа. Дело в том, что зная ключ можно без особого труда построить массив байт нужной длины, чье хэш значение совпадет с заданным. Все, что нужно -- это создать массив байт, биты которого (выбираемые extractBits()) имеют заданные значения и применить к нему basicDecrypt().
prevData существенным образом влияет на результат работы computeHash(). Поэтому в случае его отсутствия делается попытка создания более-менее случайного набора байт по значению ключа.
Создаваемое значение prevHash должно существенно изменяться при изменении ключа, а сам ключ должно быть невозможно по нему вычислить. Выбранный подход заключается в перестановке бит числа с равномерно распределенными нулями и единицами (0x55 равно 01010101).
Вероятно, алгоритм создания prevHash может быть улучшен.
hash должен всегда отличаться от нуля, т.к. нулевые байты в начале числа не влияют на его значение и после дешифрования будут потеряны, если не принять специальных мер.
Выбор 1 в качестве замены для нуля достаточно произволен -- другие значения могут оказаться более удачными. Я исходил из того, что если уж и приписывать к неизвестному (криптоаналитику) набору бит фиксированные биты, то их количество должно быть наименьшим.
hash разрезается на две половины таким образом, что при нечетном количестве байт большая половина будет расположена слева.
data делятся на bitsLen*8+1 отрезков. Позиция nj последовательно попадает на их границы. Например n0==0, а nbitsLen*8+1==data.length*8-1, т.е. это первый и последний бит data. Т.к. значение j изменяется в пределах [1, data.length*8], то первый и последний бит никогда не выбираются.
| "Нулевая" перестановка: | 0 | 1 | 2 | 3 | 4 |
| После разделения: | 3 | 4 | 0 | 1 | 2 |
4 не может следовать за 3, 1 -- за 0 и т.д.
Таким образом, все элементы (кроме среднего для нечетного количества элементов) гарантированно меняют свои места, а также изменяется их положение друг относительно друга.
Как можно видеть, количество возможных перестановок меньше чем n!. Например, существует единственная перестановка из четырех элементов, удовлетворяющая приведенным выше условиям: (3,2,1,0), т.е. все элементы выстроены в обратном порядке.
val.
-2 означает, что позиция еще не назначена. Привычное -1 не подходит, т.к. 0-1 также равно -1, т.е. с размещением нулевой позиции возникнут трудности.
b2 стало меньше делителя div -- имеет смысл снова начать с b для большего разнообразия остатков.
sub становится равной 1, если не занята следующая за только что присвоенной позиция, т.е. очередной элемент не должен в нее попасть (т.к. образуется последовательная пара) и, следовательно, количество оставшихся мест для следующей итерации нужно уменьшить на единицу.
check() является одним из ключевых условий работы криптоалгоритма. Фактически, все функции xxxEncrypt() и xxxDecrypt() полагаются на то, что переданные аргументы удовлетворяют проверяемым функцией check() условиям.
Тем не менее, вызов check() не встраивался непосредственно в тело xxxEncrypt() и xxxDecrypt(), т.к. представленная эталонная реализация создана для практического исследования свойств криптоалгоритма. В частности, для исследования его поведения при получении параметров, выходящих за рамки предусмотренных значений.
| Эталонная реализация |
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, чей код никак нельзя признать оптимальным.
| Реализация: | 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.
| Реализация, 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.
Фактически, и на сегодняшний день конференция RU.CRYPT является наилучшим местом для обсуждения DersCrypt и связанных с ним криптографических вопросов.
Ключевым источником информации для ее создания безусловно являлась дискуссия с участием специалистов из RU.CRYPT, которым я чрезвычайно признателен. В виду отсутствия явных ошибок, никакого обсуждения версии 1.0 в конференции RU.CRYPT не было.
Тем не менее, ссылки на DersCrypt разошлись по Рунету и дискуссия продолжилась в рамках другой аудитории. На текущий момент можно констатировать, что кроме предложений по отказу от использования msb никаких принципиальных недостатков выявлено не было.
Текущая версия DersCrypt v1.1 предлагает решение проблемы msb и представляет улучшенное описание алгоритма.
Тем не менее, мне ничего не известно о действительно серьезных исследованиях DersCrypt в рамках специализированных институтов и структур. Как следствие, в течение нескольких ближайших лет алгоритм не может быть рекомендован к использованию в критически важных для безопасности целях. "Домашнее использование" безусловно оправдано.
Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.