Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | |
Тут наверное недопонимание какое-то...
25.03.04 16:07 Число просмотров: 4252
Автор: Xelator Статус: Незарегистрированный пользователь
|
> А при "делении столбиком" потребуется 256 сравнений, может
> быть, (в зависимости от результата сравнения) вычитаний
> плюс установления бита в соответствующий разряд результата
> и сдвигов в худшем случае.
Тут наверное недопонимание какое-то...
Указанная мной оценка была для операция инверсии x через x^(p-2).
Что же касатеся Ваших 256 сравнений и вычитаний, то это для деления.
Для деления же я предлагал как бы то же самое, но основанное на блочном принципе.
Т.е. вы сравниваете не бит, а блок битов. Если у вас фиксированный делитель, т.е. порождающий полином, то вы для него всегда можете заготовить все варианты чисел на которые его надо умножить, чтобы получить все значения блока. Точнее заготавливать надо варианты умноженного делителя.
Тогда можно вычитать сразу блок за один раз, а не один бит. И сравнение делать блока, а не одного бита. Скажем если побить на 8-битные блоки, то вместо 256 сравнений и возможных вычитаний будет 32, в то время как операция на 32-битной машине как для бита так и для 8-битного слова одинаковые.
Итого накладные расходы - это 256 значений делителя в таблице.
На самом же деле, если учесть что у нас трехчлены и пятичлены используются в качестве делителя, то таблица усыхает - ненулевых битов всего 3 или 5, => нужно хранить максимум два 8-битных слова и надо вычислять откуда их вычислять. Далее, на самом деле по скольку значение умноженного старшего бита будет всегда давать сравниваемый блок, то он будет зануляться, поэтому его можно занулять сразу, а не вычитать. Итого получается 2 или 4 элемента для каждого значения 8-битного блока.
Кроме того, значение блока можно очевидно использовать как индекс в этой таблицы, тогда алгоритм деления будет выглядеть примерно так для трехчлена:
// x - делимое
// y - делитель
// r - результат
r = x
for i=n/8 ; i>=0 ; i--
index = r[n];
r[n] = 0;
r[index1] ^= t1[index];
r[index2] ^= t2[index]
Здесь index1 и index2 зависят от выбранного фиксированного делителя. Ну если например он = 2^n + 2^k +1, то index1 - это расстояние от n до k а index2 - от k до 1.
Еще будет друггой эффект - некоторые блоки не удастся вот так вот просто поксорить, потому что в вышеуказанном примере ксорка происходит по выравненному на 8бит адресу, а может понадобиться поксорить например начиная с 33 бита, тогда надо иметь в таблице ни один элемент, а два, которые заранее сдвинуты, чтобы учесть такое безобразие. Это опять можно сделать заранее если полином фиксированный.
И наконец, даже если он не фиксированный перепостроение такой таблицы каждый раз может давать эффект. Это зависит от того, насколько делимое больше по порядку чем делитель. Если вы следите за такими вещами и приводите результаты вычислений всякий раз когда они могут стать больше чем степень порождающего элемента, тогда делимое может быть максимум вдвое шире делителя.
Но даже в этом случае, вроде бы можно перестраивать таблицу на ходу.
У меня это было давно, во времена Пентиума 1. Может раскладка затрат и поменялась.
|
|
<theory>
|
Быстрая дешифровка секретов в распределениях ключей по Diffie-Hellman на эллиптических кривых. Черновик. 11.11.03 16:01
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 12.11.03 13:18 Количество правок: 4
|
Быстрая дешифровка секретов в распределениях ключей по Diffie-Hellman на эллиптических кривых.
Всем привет! Выкладываю черновик статьи в надежде получить ценные замечания, советы и предложения или просто огрестись за свои ошибки... :)
Черновик статьи.
I. Введение.
Данная статья посвящена новому методу атак методов DH на эллиптических кривых с ключами многоразового использования с использованием «несуществующей точки». Строго говоря, как и в известной «атаке по таймеру» [1] речь идёт не столько об ошибках самого метода и/или программистов, а о скрытых ловушках, возникающих при общепринятых методах эффективной реализации коммутативных операций над кривыми групп Fp и F2k.
Метод, предложенный Диффи-Хэллманом в прошлом столетии и по сей день считается наиболее эффективным способом аутентификации.
Суть его очень проста – шифрование с открытым ключём используется только для генерации общего для двух пользователей симметричного ключа, с помощью которого и идёт обмен информацией. Матаппарат также несложен:
Пусть y1=a^x1 %p и y2=a^x2%p открытые ключи пользователей. Тогда они могут рассчитать известный только им общий ключ по формуле
Q=a^x1^x2==y1^x2==y2^x1;
Адаптация этого метода к эллиптическим кривым любой группы также несложна – нужно лишь заменить операцию возведения в степень операцией умножения. :)
Y1=x1*A; Y2=x2*A;
Q=x1*x2*A===x2*Y1==x1^Y2;
Описание ошибки.
Главная потенциальная слабость этого метода довольно очевидна - атакуемому объекту приходится выполнять операции над значениями, предоставленными посторонним лицом. Отчасти этот недостаток нивелируется тем, что при передачи значения происходит возврат не рассчитанного ключа, а лишь зашифрованного им значения, но это ограничение нередко можно обойти.
На этом, например, основаны атаки на «чётный бит» или метод малых групп.
Поэтому на реализацию DH обычно налагают доп. требования, например простоту (p-1)/2 в стандартном методе, или простой порядок группы точек в EC.
IMHO, в реализации над эллиптическими кривыми это уже не является панацеей, особенно с учётом того, что длина ключа резко снижается.
Дело в том, что, например, при подобной процедуре аутентификации ничто не мешает передать значения координат вообще не существующей реально точки, такой, чтобы выдаваемое значение имело какие-то характерные фрагменты. Вообще-то это может произойти и совершенно случайно, благодаря чему собственно и была обнаружена эта ошибка.
Беглый просмотр ряда коммерческих реализаций и просто библиотек показал, что практически не одна из них не утруждает себя не то, что тестированием точки на принадлежность к группе, но и фильтрацией несуществующих точек вообще.
На первый взгляд эта возможность не открывает каких-либо серьёзных перспектив, т.к. итоговый ключ всё равно не виден, но ниже показано, что выбирая специальные (нереальные) сочетания значений координат , можно резко ограничить перечень возможных значений выдаваемого симметричного ключа и определить его простым перебором, получая в награду ценнейшую информацию об секретном ключе.
Конкретные решения зависят от атакуемой реализации, ниже приведено два простейших из них для эллиптических кривых ( в полях Fp и F2k, стандартизированных (FIPS 186-2) ).
Примеры простейших дешифровок
1. Дешифровка в поле Fp.
Если у Вас под рукой есть какая-нибудь библиотека или приложение для работы с EC попробуйте выполнить операцию удвоения с точкой вида (z,0).
Если исходить из формул -
(x;y)+(x;y)=(x3;y3)
x3=( (3x^2+a)/2y) ^2 - 2x mod p;
y3=(3x^2+a)*(x-x3)/2y -y mod p;
результатом должно быть прерывание "Деление на ноль". Не надейтесь! Ни один из вызовов аварийно не завершится!
90 % библиотек (например crypto++, ECLib) выдали точку (0,0) [point of infinity] ! Оставшиеся 10% (например - asmEC-intel.zip) - (2z;0) или (fastcrypto ) (z;0)!!!
Наиболее интересный случай 2 объясняется просто:
Дело в том, что вместо операции деления на практике используется умножение на число обратное делителю, которое находится по теореме ферма (y'=y^(p-2) mod p) или модифицированному методу Eвклида.
x3=( (3x^2+a)*(2y)^(p-2) ) ^2 - 2x
При y=0 формула существенно упрощается
x3= -2x;
y3= 0;
Поскольку в правильном множестве точек деления на ноль (y=0) не могло возникнуть по определению, то этот случай по видимому и не отслеживался (в целях оптимизации).
Случай 1 объясняется ещё проще - большинство авторов библиотек, зная что точек c y=0 не существуют, используют это значение как признак нулевой точки (в целях экономии памяти) и воспринимают задание как операцию с нулевой точкой, возвращая предопределённое zero.
Случай 3 - объяснить не могу, наверное это результат какой-то обработки DivideByZero.
Для нас особенно интересен случай 2.
Рассмотрим стандартную реализацию умножения точки на скаляр
Q=xY;
T=Y
FOR i= 0 TO bitsize(x)-1
T= T+T; -- операция удвоения T=2T
if bit(x,i)=1 then
Y=Y+T;
...
NEXT
Нетрудно видеть, что при отсутствии проверки деления (случай 2) последовательность значений T со стартовым значением (z,0) будет иметь вид
(z;0) , (-2z;0), (4z;0) … ((2^i)z;0)
а результирующее Q - сумму этих значений в поле x с учётом побитовых коэффициентов.
_x(Q)= bit(k,1)*z- bit(k,2)*2z+ bit(k,2)*4z - ... = Sum( (-2)^i* bit(k,i)*z)
_y(Q)=0
Таким образом получается ослабленные ключи, которые вполне реально вскрыть за разумное время.
Подставляя различные стартовые значения для z можно построить обычную систему уравнений длиной порядка bitsize(p), решение которой тривиально.
2) Дешифровка в поле F2m.
Наиболее перспективными на сегодня считаются кривые в бинарных полях, т.к. операции над ними занимают выполняются быстрее. Недавно FIPS-186 дополнен из списком из семи кривых этой группы, кроме того, к использованию рекомендованы кривые Koblitz'a (b=1).
Вспомним одно из их свойств :
(x;y) + (x;x+y) = 0 (point of infinity);
Очевидно, что точка (0;z) вполне удовлетворяет обоим требованиям, следовательно операция T+T выдаст нулевую точку (кстати, точка (0;b) формально является реально существующей точкой кривой, хотя и не входящей в циклическую группу.) Соответственно, результатом операции k*(0;z) будет точка (0,z) если k нечётное или нулевая точка если k mod 2=0.
Таким образом мы узнали первый бит секретного ключа, далее d1.
Рассмотрим операцию удвоения (x;y)+(x;y).
x3=x*x + b/(x*x); (в поле F2m)
при x3=0 следует x*x+b(x*x)==0 или x^4=-b (в поле F2m)
Отсюда следует, что операция удвоения точки
(m1;z1) где m^4=-b ( поля F2m) даст точку (0,z),
соответственно k*(m;z1) будет иметь два варианта в зависимости от значения предпоследнего бита = bit(k,1)*(m;z1)+ d1*(0;z), осталось только перебрать их.
Значения следующих битов мы можем установить решая уравнения
x^4+mi*x^2+b=0 в простом бинарном поле и подставляя их в качестве исходных точек.
Разумеется реальность нижеописанной атаки зависит от реализации - что проверяется первым - совпадение точек или их противоположность.
Полагаю, вариьируя значения точек, можно предложить ещё много вариантов атаки, я рассмотрел лишь самые очевидные случаи.
Пока, всё! Большая просьба высказывать свои замечания и предложения. Не исключено, что я где-то сильно ошибаюсь, поэтому и публикую данный черновик в форуме.
|
|
Elliptic Curve Coding 12.11.03 18:50
Автор: Persicum Статус: Незарегистрированный пользователь
|
Насколько я понимаю, под эллиптической курвой подразумевается
у^2=x^3 + a x + b
Где в сети нарыть конкретные примеры полей (простых чисел, 2^n и т.д.), коэффициентов a и b, образующих точек Q и т.д., рекомендованных для алгоритмов с открытым ключом? Не просто теорию, а готовых к реализации решений - тока запрограммируй и усе.
|
| |
Кривых много 13.11.03 00:22
Автор: Komlin Статус: Незарегистрированный пользователь
|
> Насколько я понимаю, под эллиптической курвой
> подразумевается
> у^2=x^3 + a x + b
Нет, не только. Это лишь один из вариантов.
>
> Где в сети нарыть конкретные примеры полей (простых чисел,
> 2^n и т.д.), коэффициентов a и b, образующих точек Q и
> т.д., рекомендованных для алгоритмов с открытым ключом? Не
> просто теорию, а готовых к реализации решений - тока
> запрограммируй и усе.
Да где угодно, стоит лишь запустить поисквик.
Подробное описание с рекомендованными кривыми лежит на
http://skagi.net/ecdsa.pdf
Большая подборка литературы есть на
http://www.ssl.stu.neva.ru/psw/crypto.html
А чтобы не сотрворять велосипед можно взять любу. из готовых библиотек, список которые есть например на securityfocus.com
Русскоязычный есть и на securitylab.ru
|
| | |
Кривых много 15.11.03 12:35
Автор: Persicum Статус: Незарегистрированный пользователь
|
Спасибо за ссылочки!
Ты погоди ломать то, нужно строить еще научиться! Уж лучше тормозные глючные студенческие поделки, чем готовые оптимизированные функции типа GetMyVeryStrongECCKey(512), если не знать, как они работают. Теперь я знаю как складывать и удваивать точки.
Несколько ламерских вопросов.
1) Надыбал примеры кривых.
a,b – параметры кривых.
p – простое число,
Gx,Gy – координаты Образующей Точки,
n – число элементов, или число, через которое Образующая точка начнет повторяться?
2) Как брать остатки от деления на лажевые числа мерсена типа
2^192 - 2^64 - 1 (не проводя самого деления, быстро). От нормальных чисел мерсена легко брать, а от этих – не знаю как.
3) Формулки для сложения и удвоения точек содержат деление по модулю-обратные элементы. Это ведь ОЧЧЕНЬ долго кажный раз вычислять (взять хоть евклида, хоть степень p-2)!!!
4) Если нужно умножить точку на большое число, то это типа как в степень быструю алгоритм, удвавать, удваивать, складывать с аккумулятором нужные биты, так?
5) Q=k G : k – секретное число (1<k<n), Q – открытая информация, по которой k хрен найдешь. Как же организовать шифрование и подпись, лучше симметричный случай типа RSA, или поотдельности?
|
| | | |
Можно поюзать таблицу умножения наоборот.
20.03.04 02:47
Автор: Xelator Статус: Незарегистрированный пользователь
|
> 2) Как брать остатки от деления на лажевые числа мерсена
> типа
> 2^192 - 2^64 - 1 (не проводя самого деления, быстро). От
> нормальных чисел мерсена легко брать, а от этих – не знаю
> как.
Можно поюзать таблицу умножения наоборот.
У вас трехчлен, т.е. надо будет разбить делимое на блоки, смотреть на значение блока, по нему выбирать кусок множителя, после чего блок можно занулить, и в соответствующих местах прибавить части кусок множителя на младшие члены делителя, в вашем примере:
r = d / (2^192-2^64-1), найти m такой что m*2^192 равен нескольким битам в d (количество бит равно как бы разрядности таблицы умножения), соответсвенно r1 = m1 - 2^64*m -m;где m1 = d - m*2^192.
Придется немного чиселки подвигать и "поксорить" пока d не станет меньше 2^192...
> 3) Формулки для сложения и удвоения точек содержат деление
> по модулю-обратные элементы. Это ведь ОЧЧЕНЬ долго кажный
> раз вычислять (взять хоть евклида, хоть степень p-2)!!!
>
Забыл как... кажется если взять p-2 а бинарные степени все сохранить, ну вроде того, что (p-2) = sum(j=0,k)(2^j) то там должно быть нормально - быстрое возведение в степень - это просто "раздвигание" битов на четные позиции (если мы в нормальном базисе?!).... я попробую повспоминать...
|
| | | | |
Кажется так, поправьтеесли ошибки... 24.03.04 14:10
Автор: Xelator Статус: Незарегистрированный пользователь
|
От исходной задачи рассмотрим только вычисление x^(p-2)
Пусть (p-2) n-битное число.. представим его в виде суммы его бит: (p-2) = sum(i=0,n)(2^k[i]),
здесь k[i] = {0, i} зависит от того чему равен i-ый бит в числе (p-2).
Возьмем худший вариант - все n бит в (p-2) равны 1.
Тогда (сумму будем понимать в смыле цикла for языка C, т.е. n не включается):
x^(p-2) = x^(sum(i=0,n)(2^k[i])) = x^(2^k[0]) * x^(2^k[1]) * ... x^(2^k[n-1])
Выходит нам требуется следующие вычисления в худшем случае:
1) (n-1) приведение по модулю поля для каждого x^(2^k[i])
2) (n-1) умножения приведенных результатов x^(2^k[i])
3) посчитать все x^(2^k[i]) в том числе сделать для них приведения по модулю в процессе.
так-так пункт 3) требует - n^2 возведений в квадрат и приведений по модулю (если я правильно считаю арифмитическую прогрессию ;-))).
итого = n^2 + 2n - 2 = (n-1)^2 - 1 возведений в квадрат и приведений по модулю
Т.е. для 256-битного числа (хотя модульгый трехчлен вроде был 191 степени?) получается
65524 возведений в квадрат и приведений по модулю.
Выходит критическая масса сидит в умножениях - умножайте быстро!
Возведение в квадрат в бинарном поле это "раздвигание" бит по четным позициям.
Быстрое приведение на трехчлен (то же для пятичлена) обсуждалось выше.
|
| | | | | |
А при "делении столбиком" потребуется 256 сравнений, может... 24.03.04 14:49
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 24.03.04 14:51 Количество правок: 1
|
> Т.е. для 256-битного числа (хотя модульгый трехчлен вроде
> был 191 степени?) получается
> 65524 возведений в квадрат и приведений по модулю.
> Выходит критическая масса сидит в умножениях - умножайте
> быстро!
А при "делении столбиком" потребуется 256 сравнений, может быть, (в зависимости от результата сравнения) вычитаний плюс установления бита в соответствующий разряд результата и сдвигов в худшем случае.
|
| | | | | | |
Тут наверное недопонимание какое-то...
25.03.04 16:07
Автор: Xelator Статус: Незарегистрированный пользователь
|
> А при "делении столбиком" потребуется 256 сравнений, может
> быть, (в зависимости от результата сравнения) вычитаний
> плюс установления бита в соответствующий разряд результата
> и сдвигов в худшем случае.
Тут наверное недопонимание какое-то...
Указанная мной оценка была для операция инверсии x через x^(p-2).
Что же касатеся Ваших 256 сравнений и вычитаний, то это для деления.
Для деления же я предлагал как бы то же самое, но основанное на блочном принципе.
Т.е. вы сравниваете не бит, а блок битов. Если у вас фиксированный делитель, т.е. порождающий полином, то вы для него всегда можете заготовить все варианты чисел на которые его надо умножить, чтобы получить все значения блока. Точнее заготавливать надо варианты умноженного делителя.
Тогда можно вычитать сразу блок за один раз, а не один бит. И сравнение делать блока, а не одного бита. Скажем если побить на 8-битные блоки, то вместо 256 сравнений и возможных вычитаний будет 32, в то время как операция на 32-битной машине как для бита так и для 8-битного слова одинаковые.
Итого накладные расходы - это 256 значений делителя в таблице.
На самом же деле, если учесть что у нас трехчлены и пятичлены используются в качестве делителя, то таблица усыхает - ненулевых битов всего 3 или 5, => нужно хранить максимум два 8-битных слова и надо вычислять откуда их вычислять. Далее, на самом деле по скольку значение умноженного старшего бита будет всегда давать сравниваемый блок, то он будет зануляться, поэтому его можно занулять сразу, а не вычитать. Итого получается 2 или 4 элемента для каждого значения 8-битного блока.
Кроме того, значение блока можно очевидно использовать как индекс в этой таблицы, тогда алгоритм деления будет выглядеть примерно так для трехчлена:
// x - делимое
// y - делитель
// r - результат
r = x
for i=n/8 ; i>=0 ; i--
index = r[n];
r[n] = 0;
r[index1] ^= t1[index];
r[index2] ^= t2[index]
Здесь index1 и index2 зависят от выбранного фиксированного делителя. Ну если например он = 2^n + 2^k +1, то index1 - это расстояние от n до k а index2 - от k до 1.
Еще будет друггой эффект - некоторые блоки не удастся вот так вот просто поксорить, потому что в вышеуказанном примере ксорка происходит по выравненному на 8бит адресу, а может понадобиться поксорить например начиная с 33 бита, тогда надо иметь в таблице ни один элемент, а два, которые заранее сдвинуты, чтобы учесть такое безобразие. Это опять можно сделать заранее если полином фиксированный.
И наконец, даже если он не фиксированный перепостроение такой таблицы каждый раз может давать эффект. Это зависит от того, насколько делимое больше по порядку чем делитель. Если вы следите за такими вещами и приводите результаты вычислений всякий раз когда они могут стать больше чем степень порождающего элемента, тогда делимое может быть максимум вдвое шире делителя.
Но даже в этом случае, вроде бы можно перестраивать таблицу на ходу.
У меня это было давно, во времена Пентиума 1. Может раскладка затрат и поменялась.
|
| | | | | | | |
Тут наверное недопонимание какое-то... 25.03.04 16:36
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Тут наверное недопонимание какое-то...
Естесственно, поэтому и хочется поподробнее разобраться, наверняка тут на форуме не я один всего этого непонял.
Ковыряюсь тут над библиотечкой, работающей с большими числами, так вот у меня деление пока получается в 50 раз медленнее умножения. Хотелось бы достичь эквивалентной скорости.
> Указанная мной оценка была для операция инверсии x через
> x^(p-2).
>
> Что же касатеся Ваших 256 сравнений и вычитаний, то это для
> деления.
> Для деления же я предлагал как бы то же самое, но
> основанное на блочном принципе.
Вот это и интересно, может поэтому и умножение у меня быстрее, что я его по-другому от деления реализовал, "по блочному принципу". Пока не догадался как это с делением сделать.
> Т.е. вы сравниваете не бит, а блок битов. Если у вас
Естественно, когда я сравниваю делимое и делитель, я сравниваю поблочно - кусками по 32 бит в соответствии с ИА32 архитектурой.
> фиксированный делитель, т.е. порождающий полином, то вы для
> него всегда можете заготовить все варианты чисел на которые
> его надо умножить, чтобы получить все значения блока.
> Точнее заготавливать надо варианты умноженного делителя.
> Тогда можно вычитать сразу блок за один раз, а не один бит.
> И сравнение делать блока, а не одного бита. Скажем если
> побить на 8-битные блоки, то вместо 256 сравнений и
Если бы деление можно было реализовать еще проще/быстрее чем "столбиком", как учат в начальной школе, то, наверное, и учили бы по-другому.
> возможных вычитаний будет 32, в то время как операция на
> 32-битной машине как для бита так и для 8-битного слова
> одинаковые.
> Итого накладные расходы - это 256 значений делителя в
> таблице.
Дык у меня 8 вычитаний 32битных блоков и получается.
В двоичной системе легче делить, чем в десятиричной, там умножать не надо, поскольку умножение на 0 дает 0, а умножение на 1 дает само число.
Естественно, если делитель больше делимого, то результат 0 и делить ничего не надо.
Двигаем делитель, пока старшие биты не займут одинаковые позиции, далее цикл если делимое больше делителя (сдвинутого), то вычитаем одно из другого и ставим 1 в соответствующий разряд результата, двигаем вправо делитель. Деление столбиком напоминает, без умножения, естественно?
Фрагмент функции представить для общего обозрения?
Если не трудно (имеется в наличии) - представте вашу идею на алгоритмическом языке...
|
| | | | | | | | |
Поправки 26.03.04 18:49
Автор: Xelator Статус: Незарегистрированный пользователь
|
К сожалению нет у меня уже исходников - ну ооочень давно было дело.
Попробуем еще раз на словах.
1) простое деление столбиком, которое используете вы содержит
- сравнение старшего бита делимого с делителем.
в первый раз они всегда равны, затем после первого вычитания следующие страшие биты делимого могут быть нулями.
- сдвиг делителя, чтобы его старший бит стоял там же где и текущий старший бит делимого
- вычитания делителя из делимого
И так по кругу. Если у вас делитель 256-битный, а делимое 512-битное (после умножения двух 256-битных чисел например), то потратим 256 сравнений, и в худшем случае 256 сдвигов 256-битного делителя и 256 вычитаний делителя из делимого. Если предположить что у нас поровну нулей и единиц в делимом (это ведь криптография и должно быть равномерное распределение?), то в среднем 128 сдвигов и вычитаний делителя.
2) блочное деление, которое я описывал дляфиксированногоделителя. если делитель нефиксированный, то ко времени работы алгоритма надо добавить время построения таблицы.
в нашем случае в роли делителя должен выступать порождающий элемент, т.е. величина фиксированная.
предварительные действия - они же генерация таблицы:
- выбрать размер таблицы , он же ширина блока. Возьмем 8 бит, размер таблицы тогда 256 ячеек.
- получить все числа такие, что они при умножении на делитель генерируют результат, у которого старшие 8 бит принимают всевозможные значения. Таковых должно быть 256 в нашем случае.
Получив таковые числа, построить таблицу, в которой каждый элемент равен результату умножения делителя на одно из чисел. Отсортировать эту таблицу по значению старших 8 бит результата.
Слов много, а на самом деле делов на полкопейки - например, берете полином у которого старшие биты поочередно заполняете 256 возможными значениями и делите обычным алгоритмом. Получается то, что нужно само собой.
Теперь блочный алгоритм деления.
- прочитать старший 8-битный блок 512-битного делимого
- по его значению выбрать элемент из таблицы (помните, мы ее сортировали так, чтобы само значение могло быть одновременно и индексом)
- вычесть 256-битное табличное значение из делимого
Итого сложность в операциях = 256/8 = 32 блока => 32 раза прочитать 8-битный блок из делимого, по этому индексу 32 раза прочитать 256-битное табличное значение и 32 вычесть это табличное значение.
У первого алгоритма = 256 сравнений, 128 сдвигов и 128 вычитаний
У второго = 32 чтения из делимого, 32 чтения из таблицы, 32 вычитания.
Надо понимать, что чтения здесь не стоят ничего - это просто адреса для вычитания.
Итого в 8 раз меньше вычитаний, нет вообще 128 сдвигов и 256 сравнений.
Прокатывает объяснение? Если да, то продолжим для трехчленов и пятичленов.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
