Использование библиотеки FreeLIP для расчетов с длинными числами
Использование библиотеки FreeLIP для расчетов с длинными числами
Информация и исходный код, приведенные в данной статье использовались при выполнении экспериментальной части работы «Разработка и исследование нейросетевых архитектур для выполнения асимметричных криптографических преобразований», выполняемой при поддержке Федерального агентства по науке и инновациям и Совета по грантам Президента Российской Федерации, грант МК-4190.2007.9.
Free Long Integer Package (Free LIP) – одна из наиболее известных библиотек для работы с длинными числами с открытым исходным кодом [1]. Free LIP разработана Arjen K. Lenstra [2] в период с 1989 по 1998. Библиотека является очень мощным, легким в использовании и довольном быстрым средством для выполнения математических операций с длинными числами. Библиотека написана на языке Си, и таким образом может быть легко использована в приложениях на различных операционных системах. Хотя библиотека хорошо документирована и снабжена примерами некоторые разработчики имеют проблемы при компиляции библиотеки в средах Visual Studio и Borlad C++. Ниже приведен пример расчетов для криптоситемы Меркла-Хэллмана с использованием библиотеки Free LIP c пояснениями. Проект для среды разработки Visual Studio 2003 скачать здесь.
Пример
#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include "lip.h" // подключение заголовочных файлов библиотеки
#include <time.h>
#define SEQLEN 256
#define BITLEN 256
static verylong seq_a_d[SEQLEN]; // создание массива длинных чисел длиной 256 байт
static verylong seq_a[SEQLEN];
verylong seqentry= 0;
verylong seqsum = 0;
verylong encrypted = 0;
verylong ks_m = 0;
verylong ks_w = 0;
verylong ks_w_inv = 0;
int i;
long plain[SEQLEN];
long decrypted[SEQLEN];
// Генерация сверхвозрастающей последовательности
zrstarts((long)time( NULL )); // Инициализация генератора псевдослучайных чисел
zsmul(seqsum,0,&seqsum);
for (i=0;i<SEQLEN;i++) {
// Создание простого целого числа длиной 256
if (zrandomprime(BITLEN, 5, &seqentry, zrandomb)) {
if (zcompare(seqsum,seqentry)) // 3.
zadd(seqentry,seqsum,&seqentry);
zadd(seqentry,seqsum,&seqsum);
zsmul(seqentry,1,&(seq_a_d[i]));
} else {
return -1;
printf("Couldn`t generate sequence\n");
}
}
// генерация ключевой пары
zadd(seq_a[i],seqsum,&seqsum);
while (1) {
zrandomprime(BITLEN*2, 5,&ks_m,zrandomb);
zwriteln(ks_m);
if (zcompare(ks_m,seqsum)>=1)
break;
}
while (1) {
zrandomprime(BITLEN, 5,&ks_w,zrandomb);
if (zcompare(seqsum,ks_w)>=1)
break;
}
// вычисление модульной инверсии
zinvmod(ks_w,ks_m,&ks_w_inv);
// расчет открытого ключа
for (i=0;i<SEQLEN;i++) {
zmulmod(seq_a_d[i],ks_w,ks_m,&(seq_a[i]));
}
// шифрование x
zsmul(seqsum,0,&seqsum);
for (i=0;i<SEQLEN;i++) {
zsmul(seq_a[i],plain[i],&seqentry);
zadd(seqentry,seqsum,&seqsum);
}
zsmul(seqsum,1,&encrypted);
// расшифрование
zmulmod(encrypted,ks_w_inv,ks_m,&(seqsum_w));
for (i=SEQLEN-1;i>=0;i--) {
zdiv(seqsum_w,seq_a[i],&seqentry,&seqsum_w);
if (zscompare(seqentry,(long)1)==0)
decrypted[i]=1;
else
decrypted[i]=0;
}
[1] Библиотека FreeLIP http://www.netsw.org/system/libs/math/freelip-1.1.tar.gzâ
[2] Персональная страница А.Ленстры http://people.epfl.ch/arjen.lenstra