| 1 | Введение | |
| 2 | Суть криптоалгоритма | |
| 3 | Реализация для исследования | |
| 3.1 | Компиляция и запуск | |
| 3.2 | Комментарии к реализации | |
| 4 | Ретроспектива | |
| 5 | Заключение | |
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.
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.
Для наибольшего удобства неискушенных в программировании пользователей, использующих разнообразные платформы, языком реализации выбрана 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.
| DersCrypt.java |
|---|
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.stml.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();
}
}
|
req. Очевидно, что весь поток данных (длины length) можно разбить на блоки длины [req, req*2[.
На текущий момент была выбрана простейшая схема, в которой все блоки кроме последнего имеют одну и ту же длину -- req. Польза такого выбора в том, что количество перестановок, создаваемых createPermutation(), будет невелико, что позволит эффективно кэшировать уже созданные перестановки не вычисляя их каждый раз заново.
Обратите внимание: параметр len функции createPermutation() -- это количество остатков, а не длина блока. Т.е. блоки одинаковой длины, вообще говоря, могут порождать разное количество остатков.
din на блоки параметр length не требуется: реализация может пытаться считывать блоки длины req*2 и передавать в blockEncrypt() их половины плюс последний блок неполной длины, требующий особой обработки. Тем не менее, я выбрал интерфейс с явным указанием длины, т.к. в противном случае алгоритм разбиения становится достаточно громоздким ничего не улучшая по сути.
Дополнительным плюсом наличия параметра length является возможность реализации других схем разбиения на блоки, например, зависящих от ключа.
prevEncr) передается в blockEncrypt() последним аргументом. В результате чего, один и тот же блок открытого текста будет порождать, как правило, различные блоки зашифрованного текста, что положительно сказывается на криптостойкости.
blockDecrypt() и изменяет значение encr, это изменение не имеет значения для computeHash(). Дело в том, что изменяется только наибольший значащий бит (msb), а extractBits() никогда не выбирает крайние биты.
null значение свидетельствует о несовпадении хэша, добавленного к блоку открытого текста перед шифрованием, с хэшем, рассчитанным по самому блоку. Причина: неверный текст для дешифрования и/или неверный ключ.
key как положительное число B2 в формате big-endian. Обратите внимание: нулевые байты в начале массива key никак не влияют на значение B2.
hash должен всегда отличаться от нуля, т.к. нулевые байты в начале числа не влияют на его значение и после дешифрования будут потеряны, если не принять специальных мер.
Выбор 1 в качестве замены для нуля достаточно произволен -- другие значения могут оказаться более удачными. Я исходил из того, что если уж и приписывать к неизвестному (криптоаналитику) набору бит фиксированные биты, то их количество должно быть наименьшим.
appendHash(plain, hash) к числу A1 добавляется хэш, т.е. число A'1 получается из A1 путем дописывания хэша, рассчитанного по A1.
A'2 (результат шифрования A'1) в массив байт encr и отбрасываем начальные нули.
B2.
Для того, чтобы не потерять эти начальные нули можно пойти несколькими путями: сохранять в выходном потоке общее количество остатков или же записывать в нулевой остаток некоторую константу и помечать, что старший остаток должен быть обнулен перед дешифрованием.
Я выбрал второй путь: если старший значащий остаток равен 1, то наибольший значащий бит (msb) зашифрованного текста свидетельствует о том, должен ли он быть обнулен (msb==1) перед дешифрованием. В любом случае, сам msb перед дешифрованием должен обнуляться, т.к. он всегда приписывается к результату шифрования, а не является частью числа A'2.
Если же старший значащий остаток не равен 1, то значение msb игнорируется и, следовательно, должно быть случайным. Для получения псевдослучайного бита используется вызов xorAllBits(hash).
Выбор единицы в качестве замены для нулевого остатка достаточно произволен. Единица хороша в плане минимизации заранее известного количества бит, в то же время, единица в начальном остатке практически всегда сокращает длину зашифрованого текста, т.е. с этой точки зрения лучше использовать константу вдвое короче ключа (т.е. log2(Const) примерно равен log2().
B2)/2
blockEncrypt() является число A'2 с дописанным наибольшим значащим битом.
Например, существует очевидная атака на базовый алгоритм шифрования/дешифрования: если на вход алгоритма подать два числа, отличающиеся только значением младшего значащего бита, то разность полученных после шифрования/дешифрования чисел будет равна B2n (для некоторого n). Т.е. если бы в случае несовпадения хэша blockDecrypt() возвращала бы массив decr, описанная выше атака была бы возможна и против DersCrypt.
blockDecrypt() изменяет значение одного из своих параметров, что, вообще говоря, неправильно с точки зрения концептуальной чистоты интерфейса. Тем не менее, это изменение не вызывает проблем в текущей реализации DersCrypt, так что я посчитал неоправданным создание копии массива encr для предотвращения побочных эффектов.
decr будет первым байтом дописанного в blockEncrypt() хэша, чье значение гарантированно отличается от нуля.
computeHash() не должна применяться для получения хэш значений в случае заранее известного ключа. Дело в том, что зная ключ можно без особого труда построить массив байт нужной длины, чье хэш значение совпадет с заданным. Все, что нужно -- это создать массив байт, биты которого (выбираемые extractBits()) имеют заданные значения и применить к нему basicDecrypt().
prevData существенным образом влияет на результат работы computeHash(). Поэтому в случае его отсутствия делается попытка создания более-менее случайного набора байт по значению ключа.
Создаваемое значение prevHash должно существенно изменяться при изменении ключа, а сам ключ должно быть невозможно по нему вычислить. Выбранный подход заключается в перестановке бит числа с равномерно распределенными нулями и единицами (0x55 равно 01010101).
Вероятно, алгоритм создания prevHash может быть улучшен.
data делятся на bitsLen*8+1 отрезков. Позиция nj последовательно попадает на их границы. Например n0==0, а nbitsLen*8+1==data.length*8-1, т.е. это первый и последний бит data. Т.к. значение j изменяется в пределах [1, data.length*8], то первый и последний бит никогда не выбираются.
hash разрезается на две половины таким образом, что при нечетном количестве байт большая половина будет расположена слева.
data, т.к. старший бит уже равен 1.
flagMsb в зависимости от значения старшего остатка.
b производится простым последовательным делением. Более эффективным является деление a на две примерно равные части (делим на bn для некоторого n) и рекурсивного применения той же процедуры к оставшимся частям.
b.
| "Нулевая" перестановка: | 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, если не занята следующая за только что присвоенной позиция, т.е. очередной элемент не должен в нее попасть (т.к. образуется последовательная пара) и, следовательно, количество оставшихся мест для следующей итерации нужно уменьшить на единицу.
2длина ключа.
В силу того, что нули в начале числа не имеют значения, реальная длина ключа (т.е. позиция старшего ненулевого бита) заведомо существенно меньше длины переданного массива байт. Если переданное значение ключа действительно нужно использовать, то начальные нули необходимо удалить, например с помощью stripLeadingZeros().
Четные значения ключа использовать не рекомендуется в силу того, что B1 и B2 должны быть взаимно простыми числами, а в нашем случае B1 -- это 2, а B2 равно значению ключа.
Нетрудно видеть, что требование взаимной простоты является одним из ключевых условий стойкости криптоалгоритма. Так, например, если в качестве ключа взять 256==28, то вся работа алгоритма сведется к простой перестановке байт.
Безусловно, ограничение на минимальную длину открытого текста не очень удобно на практике. Тем не менее, криптостойкость алгоритма существенным образом зависит от количества переставляемых в basicEncrypt() остатков (например, если количество остатков равно 1, то возвращаемое значение A2 будет равно переданному A1, т.е. никакого шифрования не получится вообще).
Наиболее очевидным решением проблемы недостаточной длины открытого текста является его "разбавление" случайными байтами до нужной длины непосредственно перед шифрованием и отбрасывание добавленных байт после дешифрования. Тем не менее, я не стал встраивать эту функциональность в текущую версию DersCrypt, т.к. не вполне определился с деталями возможной реализации в силу того, что некоторые частные случаи ее применения не должны снижать общую криптостойкость алгоритма.
check() является одним из ключевых условий работы криптоалгоритма. Фактически, все функции xxxEncrypt() и xxxDecrypt() полагаются на то, что переданные аргументы удовлетворяют проверяемым функцией check() условиям.
Тем не менее, вызов check() не встраивался непосредственно в тело xxxEncrypt() и xxxDecrypt(), т.к. представленная реализация DersCrypt создана для практического исследования свойств криптоалгоритма. В частности, для исследования его поведения при получении параметров, выходящих за рамки предусмотренных значений.
Как можно видеть, текущая редакция криптоалгоритма заметно отличается от того, что было представлено в самом начале. Ключевым источником информации для изменений безусловно является дискуссия с участием специалистов из RU.CRYPT, которым я чрезвычайно признателен.
Фактически, на сегодняшний день конференция RU.CRYPT является наилучшим местом для обсуждения DersCrypt и связанных с ним криптографических вопросов.
Тем не менее, использованные идеи и уже полученные результаты, в некотором смысле, открывают абсолютно новое поле для дискуссии. Например, исследование отдельных свойств криптоалгоритма, а также его модификаций, вполне может стать темой научных работ студентов профильных ВУЗов.
Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.