Новый криптографический алгоритм
Посвящается Механико-математическому факультету Белорусского Государственного
Университета.
Данное письмо определяет новый симметричный алгоритм шифрования (криптоалгоритм)
и содержит реализацию, пригодную для практического тестирования.
Криптоалгоритм обладает следующими достоинствами:
1. Нет ограничений на длину ключа.
2. Криптоалгоритм предельно прост для понимания и реализации.
3. Криптоалгоритм является стойким (не доказано), открытым и свободным
для использования. Я являюсь его изобретателем и утверждаю: криптоалгоритм
предназначен для свободного использования.
По сути, криптоалгоритм основан на преобразовании числа из одной системы
счисления в другую: число преобразовывается в другую систему счисления, "цифры"
переставляются, и результат возвращается в исходную систему счисления.
Описание криптоалгоритма:
- Текст для шифрования считается (длинным) целым беззнаковым числом. Обозначим
его буквой A.
- Аналогично, ключ для шифрования считается целым беззнаковым числом B.
0. Текст для шифрования сжимается для преобразования в относительно
случайную (т.е. несжимаемую) последовательность байт посредством некоторого
алгоритма сжатия. Полученная последовательность байт является числом A.
1. A разлагается в последовательность остатков от деления на B.
2. Последовательность остатков переставляется. Алгоритм перестановки
задается значением B.
3. Полученная последовательность остатков преобразовывается в число A2.
- A2 является результатом шифрования A.
Следующая Java программа предназначена для практического тестирования. Она
является полноценной реализацией криптоалгоритма (без предварительной
компрессии).
-------------------------------- A.java --------------------------------
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.math.BigInteger;
import java.util.LinkedList;
import java.util.ListIterator;
public class A
{
public static void main(String[] args) throws Exception
{
if (args.length!=4) badArgs();
String scmd=args[0];
String skey=args[1];
String sin=args[2];
String sout=args[3];
if ( !("e".equals(scmd) || "d".equals(scmd)) ) badArgs();
boolean encrypt="e".equals(scmd);
BigInteger b=new BigInteger(1, readFile(skey, 0));
if (encrypt) {
byte[] adata=readFile(sin, 1);
// append positive most significant (random) byte
for (int i=1; i<adata.length; i++) adata[0]^=adata[i];
adata[0]&=(byte)0x7f; // clear 10000000 bit
adata[0]|=(byte)0x40; // set 01000000 bit
BigInteger a=new BigInteger(adata);
BigInteger[] rems=computeRemainders(a, b);
BigInteger[] rems2=permute(rems, b, false);
BigInteger a2=computeNumber(rems2, b);
writeFile(sout, a2.toByteArray(), 0);
}
else {
BigInteger a=new BigInteger(readFile(sin, 0));
BigInteger[] rems=computeRemainders(a, b);
BigInteger[] rems2=permute(rems, b, true);
BigInteger a2=computeNumber(rems2, b);
writeFile(sout, a2.toByteArray(), 1);
}
}
private static void badArgs()
{
System.err.println("Invalid args. Must be:");
System.err.println("e|d key_file input_file output_file");
System.exit(1);
}
private static byte[] readFile(String fname, int off) throws Exception
{
File f=new File(fname);
FileInputStream fin=new FileInputStream(f);
try {
int len=(int)f.length();
byte[] ret=new byte[len+off];
fin.read(ret, off, len);
return ret;
}
finally { fin.close(); }
}
private static void writeFile(String fname, byte[] data, int off)
throws Exception
{
FileOutputStream fout=new FileOutputStream(fname);
try { fout.write(data, off, data.length-off); }
finally { fout.close(); }
}
public static BigInteger[] computeRemainders(BigInteger a, BigInteger b)
{
LinkedList lst=new LinkedList();
while (!a.equals(BigInteger.ZERO)) {
BigInteger[] qr=a.divideAndRemainder(b);
lst.add(qr[1]);
a=qr[0];
}
return (BigInteger[])lst.toArray(new BigInteger[lst.size()]);
}
public static BigInteger computeNumber(BigInteger[] rems, BigInteger b)
{
BigInteger a=BigInteger.ZERO;
for (int i=rems.length-1; i>=0; i--) {
a=a.multiply(b);
a=a.add(rems[i]);
}
return a;
}
public static BigInteger[] permute(BigInteger[] rems, BigInteger b,
boolean inverse)
{
int len=rems.length;
BigInteger[] ret=new BigInteger[len];
int pos[]=createPermutation(len, b, inverse);
for (int i=0; i<len; i++) ret[pos[i]]=rems[i];
return ret;
}
public static int[] createPermutation(int len, BigInteger b, boolean inverse)
{
int[] ret=new int[len];
LinkedList lst=new LinkedList();
for (int i=0; i<len; i++) lst.add(new Integer(i));
BigInteger b2=b;
for (int div=len; div>=1; div--) {
BigInteger bdiv=new BigInteger(""+div);
if (div==len) // always move
bdiv=bdiv.subtract(BigInteger.ONE); // most significant remainder
if (b2.compareTo(bdiv)<0) b2=b; // restart from b
BigInteger[] qr=b2.divideAndRemainder(bdiv);
b2=qr[0];
int rem=qr[1].intValue();
ListIterator lit=lst.listIterator(rem);
ret[div-1]=((Integer)lit.next()).intValue();
lit.remove();
}
if (inverse) {
int[] ret2=new int[len];
for (int i=0; i<len; i++) ret2[ret[i]]=i;
return ret2;
}
return ret;
}
}
-----------------------------------8<-----------------------------------
Для компиляции нужно набрать:
javac A.java
После чего появится файл A.class.
Для шифрования файла input_file с использованием ключа key_file:
java A e key_file input_file output_file
Результат будет помещен в output_file.
Для расшифрования файла output_file с использованием ключа key_file:
java A d key_file output_file input_file2
Результат будет помещен в input_file2 и должен полностью совпадать с исходным
файлом input_file.
Замечания по реализации:
0. Важность предварительного сжатия заключается в увеличении
криптостойкости (увеличивается вероятность того, что полученные при разложении
остатки не будут повторяться, что улучшает качество процесса перестановки; на
практике, значения остатков повторяются крайне редко, т.к. их количество
существенно меньше значения B). На алгоритм сжатия не налагается каких-либо
особых требований, обычное кодирование Хаффмана вполне подойдет.
1. Алгоритм перестановки должен основываться на значении ключа и
выбирать перестановку равновероятным образом. Он также обязан всегда передвигать
старший остаток, т.к. начальные байты зашифрованного текста должны отличаться от
оригинала. Использованный алгоритм перестановки достаточно прямолинеен и,
вероятно, может быть улучшен.
2. Значение числа, очевидно, не зависит от начальных нулей, но они не
должны теряться в процессе шифрования/расшифрования A. Поэтому перед
шифрованием к числу A приписывается ненулевой байт -- в процессе записи
расшифрованного числа он будет отброшен.
3. Тип данных BigInteger является знаковым, а старший бит задает знак
числа. Т.к. алгоритм оперирует беззнаковыми целыми, для считывания числа B
необходимо использовать специальный вид конструктора BigInteger, позволяющий
принудительно задать знак. Т.к. этот конструктор может добавлять дополнительный
нулевой байт в начало числа, он не используется при считывании A. Вместо этого,
старший бит добавляемого к A байта всегда обнуляется.
4. Значения младших бит добавляемого к A байта рассчитываются путем
хеширования текста для шифрования. На самом деле, к A можно добавлять любое
количество байт, чьи значения могут формироваться произвольным образом
(например, с учетом текущего системного времени). В этом случае по одним и тем
же тексту для шифрования и ключу каждый раз будет получаться разный
зашифрованный текст, что существенно увеличит криптостойкость.
Рекомендации по использованию:
1. Ключ для шифрования должен состоять из случайного набора бит и быть
не короче 32 байт (т.е. 256 бит).
2. Рекомендуется использовать нечетные ключи (т.е. младший бит
последнего байта файла должен быть равен 1). В этом случае 2 и B будут взаимно
простыми числами.
3. Для повышения криптостойкости, файл для шифрования (input_file)
должен быть как минимум в 10 раз длиннее ключа. Ну а при длине менее длины
ключа никакого шифрования, очевидно, не получится.
4. Т.к. время шифрования существенно зависит от длины файлов, на
практике не имеет большого смысла использование ключей длиннее 64 байт (т.е.
512 бит), а файл для шифрования стоит разбивать на порции примерно равные
длина_ключа*1000 (т.е. 32000 для 32х байтного ключа).
Замечания:
1. Все, что я знаю про данный криптоалгоритм, изложено выше. Добавить
мне _нечего_.
2. Если у Вас возник вопрос, но внимательное изучения описания и
реализации не дает ответа, то ответ неизвестен и мне. Ничем помочь не могу.
3. Если Вы обнаружили математический изъян в криптоалгоритме или ошибку
в программе-реализации -- напишите мне на new_crypto_algorithm@yahoo.com.
Письмо должно быть коротким и иметь содержательный subject. Все остальные
письма будут проигнорированы.