Jump to content

    
Sign in to follow this  
Sagittarius

возведение в степень по модулю

Recommended Posts

Здравствуйте.

 

Для асимметричных алгоритмов применяется возведение в степень со взятием остатка от деления. Собственно библиотек с исходниками много, но все под PC, большие, толстые и избыточные. А может кто встречал реализации оптимизированные для небольших МК?

 

Спасибо.

Share this post


Link to post
Share on other sites

Не помню где взял)

Компилятор - WinAVR

#include <avr/io.h>

#define MesSize 16

void DivideByTwo ( uint8_t *x )
{
//Divides multiple-precision integer x by 2 by shifting to right by one bit
uint16_t d=0;
uint8_t i;

for ( i=0; i<MesSize; i++ )
{
	d |= x[i];
	x[i] = ( ( d >> 1 ) & 0xFF );
	if ( d & 0x01)
		d = 0x100;
	else
		d = 0;
}
}

void aSubtract ( uint8_t *a, uint8_t *b )
{
//Computes a = a - b
uint8_t i;
uint8_t borrow=0;
int16_t d;

for ( i=MesSize-1; i>=0; i-- )
{
	d = a[i] - b[i] - borrow;
	if ( d < 0 )
	{
		d = d + 0x100;
		borrow = 1;
	}
	else
		borrow = 0;
	a[i] = d & 0xFF;
}
}

void aModAdd ( uint8_t *a, uint8_t *b, uint8_t *m )
{
//Computes a = (a + b) mod m
uint8_t i;
uint16_t d=0;
uint8_t tmp=1;

//1. Add a = a + b
for ( i=MesSize-1; i>=0; i-- )
{
	d = a[i] + b[i] + d;
	a[i] = d & 0xFF;
	d >>= 8;
}
//2. If a > m then a = a - m
while ( tmp )
{
	for ( i=0; i<MesSize; i++ )
	{
		if ( a[i] != m[i] )
			break;
	}
	if ( a[i] >= m[i] )
		aSubtract( a, m );
	else
		tmp=0;
}
}

uint8_t aIsZero ( uint8_t *a )
{
//Returns true if a is zero
uint8_t i;

for ( i=MesSize-1; i>=0; i-- )
{
	if ( a[i] != 0 )
		return 0;
}

return 1;
}

void aModMult ( uint8_t *w, uint8_t *abX, uint8_t *abY, uint8_t *abMod )
{
//Returns w = (x * y) mod m
uint8_t x[MesSize];
uint8_t y[MesSize];
uint16_t nBits;
uint8_t i;

//1. Set w = 0, and temps x = abX, y = abY
for ( i=0; i<MesSize; i++ )
{
	x[i] = abX[i];
	y[i] = abY[i];
	w[i] = 0;
}
//2. From LS bit to MS bit of X do:
for ( nBits=MesSize*8; nBits>0; nBits-- )
{
	//2.1 if x is odd then w = (w + y) mod m
	if ( ( x[MesSize - 1] & 0x01 ) != 0 )
		aModAdd ( w, y, abMod );
	//2.2 x = x / 2
	DivideByTwo ( x );
	//2.3 if x != 0 then y = (y + y) mod m
	if ( aIsZero ( x ) )
		break;
	aModAdd( y, y, abMod );
}
}

void aModExp ( uint8_t *a, uint8_t *abBase, uint8_t *abExponent, uint8_t *abModulus )
{
//Computes a = b^e mod m and returns the result in a byte array as a VARIANT
uint8_t e[MesSize];
uint8_t s[MesSize];
uint16_t nBits;
uint8_t i;

//Perform right-to-left binary exponentiation
//1. Set A = 1, S = b
//NB s and e are trashed so use copies
for ( i=0; i<MesSize; i++ )
{
	s[i] = abBase[i];
	e[i] = abExponent[i];
	a[i] = 0;
}
a[MesSize-1] = 1;
//2. While e != 0 do:
for ( nBits=MesSize*8; nBits>1; nBits-- )
{
	//2.1 if e is odd then A = A*S mod m
	if ( ( e[MesSize - 1] & 0x01) != 0 )
		aModMult ( a, a, s, abModulus );
	//2.2 e = e / 2
	DivideByTwo ( e );
	//2.3 if e != 0 then S = S*S mod m
	if ( aIsZero( e ) )
		break;
	aModMult( s, s, s, abModulus );
}
}

int main ( int argc, char *argv[] )
{
uint8_t rsa_mod[MesSize];
uint8_t rsa_key[MesSize];
uint8_t in_mes[MesSize];
uint8_t out_mes[MesSize];


aModExp ( out_mes, in_mes, rsa_key, rsa_mod );

return 0;
}

Share this post


Link to post
Share on other sites
Спасибо, сравню по скорости с тем что выдрал из MatrixSSL. Код в нем точно больше чем в этом.

Это - обычный "лобовой" алгоритм модульного возведения в степень. Если нужна скорость, то про него следует забыть. Ищите "возведение в степень по Монтгомери", будет значительно быстрее. По быстрому можно выдрать из библиотеки, например, FLINT.

Share this post


Link to post
Share on other sites
Не помню где взял)

Компилятор - WinAVR

 

В паре мест есть такое

 

uint8_t i;

for ( i=MesSize-1; i>=0; i-- )

 

если uint без знаковое (судя по наличию просто int16) то это мертвый цикл. После исправления на 32-х байтовых числах работало по симулятору 98сек, результат вычислений ошибочен :-( Если делать на основе MatrixSSL то то же самое вычисляется за 10с алгоритмом возведения в квадрат и умножения. У монтгомери проблемы с ОЗУ, требуется массив из 32-х длинных чисел для промежуточных результатов. На AVR это еще нормально будет а вот в PIC18 с его гадкой страничной адресацией это уже не лезет.

Share this post


Link to post
Share on other sites
В паре мест есть такое

 

uint8_t i;

for ( i=MesSize-1; i>=0; i-- )

 

Извините, скопировал не проверив.

Все i должны быть int8_t.

Проверил в железе:

Контролер - ATMega 32

Частота - 3686400

На 32-х байтовых числах - 60 секунд. Результат правильный.

Share this post


Link to post
Share on other sites
Проверил в железе:

Контролер - ATMega 32

Частота - 3686400

На 32-х байтовых числах - 60 секунд. Результат правильный.

 

т.е. 3.68MHz? и на 32-х байтах работает всего 60 секунд??? интересный результат, буду проверять. В железе на PIC не гонял, только в симуляторе, но на 60MHz получалось 98сек. Надо будет сравнить оба проца, благо все в наличии есть :-) А проверяли на чем, если не секрет? А то пришлось собирать тест из FreeLip, проверять его по online-калькулятору и потом уже проверять код для МК, ибо HEX числа по другому в имеющиеся калькуляторы не запихивались, только десятичные :-)

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this