Аппаратная реализация RSA: проблемы умножения Radx-2 Montgomery

Я реализую RSA 1024 на аппаратном уровне (xilinx ZYNQ FPGA) и не могу выяснить несколько любопытных вопросов. В частности, я обнаружил, что моя реализация работает только для определенных комбинаций база / экспонента / модуль, но не нашел никакой причины, почему это так.

Примечание: я реализую алгоритм, используя Xilinx HLS (по сути, код C, который синтезируется в аппаратное обеспечение). Ради этого поста трактуйте его как стандартную реализацию C, за исключением того, что у меня могут быть переменные шириной до 4096 бит. Я еще не распараллелил его, поэтому он должен вести себя так же, как стандартный код Си.

Эта проблема

Моя проблема в том, что я могу получить правильный ответ для определенных задач теста модульного возведения в степень, но только если значения для основания, экспоненты и модуля могут быть записаны в гораздо меньшем количестве бит, чем фактическая ширина операнда 1024 бита (т.е. они дополнен нулями).

Когда я использую фактические 1024-битные значения, сгенерированные из SSH-keygen, я больше не получаю правильные результаты.

Например, если мои входные аргументы

uint1024_t base     = 1570
uint1024_t exponent = 1019
uint1024_t modulus  = 3337

Я правильно получаю результат 1570^1029 мод (3337) = 688

Тем не менее, когда я на самом деле использую значения, которые занимают все (или приблизительно все) 1024 бит для входов...

uint1024_t base     = 0x00be5416af9696937b7234421f7256f78dba8001c80a5fdecdb4ed761f2b7f955946ec920399f23ce9627f66286239d3f20e7a46df185946c6c8482e227b9ce172dd518202381706ed0f91b53c5436f233dec27e8cb46c4478f0398d2c254021a7c21596b30f77e9886e2fd2a081cadd3faf83c86bfdd6e9daad12559f8d2747
uint1024_t exponent = 0x6f1e6ab386677cdc86a18f24f42073b328847724fbbd293eee9cdec29ac4dfe953a4256d7e6b9abee426db3b4ddc367a9fcf68ff168a7000d3a7fa8b9d9064ef4f271865045925660fab620fad0aeb58f946e33bdff6968f4c29ac62bd08cf53cb8be2116f2c339465a64fd02517f2bafca72c9f3ca5bbf96b24c1345eb936d1
uint1024_t modulus  = 0xb4d92132b03210f62e52129ae31ef25e03c2dd734a7235efd36bad80c28885f3a9ee1ab626c30072bb3fd9906bf89a259ffd9d5fd75f87a30d75178b9579b257b5dca13ca7546866ad9f2db0072d59335fb128b7295412dd5c43df2c4f2d2f9c1d59d2bb444e6dac1d9cef27190a97aae7030c5c004c5aea3cf99afe89b86d6d

Я неправильно получаю огромное число, а не правильный ответ 29 (0x1D)

Я проверял оба алгоритма миллион раз и экспериментировал с разными начальными значениями и границами цикла, но, похоже, ничего не работает.

Моя реализация

Я использую стандартный метод квадратов и умножения для модульного возведения в степень, и я решил использовать алгоритм Tenca-Koc radix-2 для умножения Монтгомери, подробно описанный в псевдокоде ниже...

/* Tenca-Koc radix2 montgomery multiplication */
Z = 0
for i = 0 to n-1
    Z = Z + X[i]*Y
    if Z is odd then Z = Z + M
    Z = Z/2  // left shift in radix2
if (S >= M) then S = S - M

Моя реализация умножения Монтгомери выглядит следующим образом:

void montMult(uint1024_t X, uint1024_t Y, uint1024_t M, uint1024_t* outData)
{
    ap_uint<2*NUM_BITS> S = 0; 

    for (int i=0; i<NUM_BITS; i++)
    {
        // add product of X.get_bit(i) and Y to partial sum
        S += X[i]*Y; 

        // if S is even, add modulus to partial sum
        if (S.test(0))  
            S += M;     

        // rightshift 1 bit (divide by 2)
        S = S >> 1;
    }

    // bring back to under 1024 bits by subtracting modulus
    if (S >= M)
        S -= M;

    // write output data
    *outData = S.range(NUM_BITS-1,0);

}

и мое высшее модульное возведение в степень состоит в следующем, где (переключение записи!) ...

// k: number of bits
// r = 2^k (radix)
// M: base
// e: exponent
// n: modulus
// Mbar: (precomputed residue) M*r mod(n)
// xbar: (precomputed initial residue) 1*r mod(n)

void ModExp(uint1024_t M, uint1024_t e, uint1024_t n, 
            uint1024_t Mbar, uint1024_t xbar, uint1024_t* out)
{
    for (int i=NUM_BITS-1; i>=0; i--)
    {
        // square
        montMult(xbar,xbar,n,&xbar);

        // multiply   
        if (e.test(i)) // if (e.bit(i) == 1)
            montMult(Mbar,xbar,n,&xbar);
    }
        // undo montgomery residue transformation
        montMult(xbar,1,n,out);
}

Я не могу понять, почему это работает для всего, кроме фактического значения 1024 бит. Любая помощь приветствуется

Источник

2 ответа

Решение

Обновление: я наконец смог исправить проблему после того, как перенес свой дизайн на Java, чтобы проверить промежуточные значения в отладчике. Дизайн работал безупречно в Java без каких-либо изменений в структуре кода, и это подсказало мне, что происходит не так.

Проблема обнаружилась после получения правильных промежуточных значений с помощью Java-пакета BigInteger. Библиотека произвольной точности HLS имеет фиксированную битовую пропускную способность (очевидно, поскольку она синтезируется до аппаратного обеспечения), тогда как программные библиотеки BigInteger имеют гибкую битовую ширину. Оказывается, что оператор сложения обрабатывает оба аргумента как подписанные значения, если они имеют разную ширину в битах, несмотря на то, что я объявил их как неподписанные. Таким образом, когда в MSB был 1 промежуточного значения, и я пытался добавить его к большему значению, он рассматривал MSB как знаковый бит и пытался подписать его расширение.

Этого не произошло с библиотекой Java BigInt, которая быстро указала мне на проблему.

Если кто-то заинтересован в реализации модульного возведения в степень Java с использованием алгоритма radix2 Tenca-Koc для умножения Монтгомери, вы можете найти код здесь: https://github.com/bigbrett/MontModExp-radix2

Источник

Я заменил свой ответ, потому что я был неправ. Ваш оригинальный код совершенно корректен. Я проверил это, используя мою собственную библиотеку BigInteger, которая включает в себя арифметику Монтгомери, и все работает как шарм. Вот мой код:

const
  base1     =
 '0x00be5416af9696937b7234421f7256f78dba8001c80a5fdecdb4ed761f2b7f955946ec9203'+
 '99f23ce9627f66286239d3f20e7a46df185946c6c8482e227b9ce172dd518202381706ed0f91'+
 'b53c5436f233dec27e8cb46c4478f0398d2c254021a7c21596b30f77e9886e2fd2a081cadd3f'+
 'af83c86bfdd6e9daad12559f8d2747';
  exponent1 =
 '0x6f1e6ab386677cdc86a18f24f42073b328847724fbbd293eee9cdec29ac4dfe953a4256d7e'+
 '6b9abee426db3b4ddc367a9fcf68ff168a7000d3a7fa8b9d9064ef4f271865045925660fab62'+
 '0fad0aeb58f946e33bdff6968f4c29ac62bd08cf53cb8be2116f2c339465a64fd02517f2bafc'+
 'a72c9f3ca5bbf96b24c1345eb936d1';
  modulus1  =
 '0xb4d92132b03210f62e52129ae31ef25e03c2dd734a7235efd36bad80c28885f3a9ee1ab626'+
 'c30072bb3fd9906bf89a259ffd9d5fd75f87a30d75178b9579b257b5dca13ca7546866ad9f2d'+
 'b0072d59335fb128b7295412dd5c43df2c4f2d2f9c1d59d2bb444e6dac1d9cef27190a97aae7'+
 '030c5c004c5aea3cf99afe89b86d6d';

function MontMult(X, Y, N: BigInteger): BigInteger;
var
  I: Integer;
begin
  Result:= 0;
  for I:= 0 to 1023 do begin
    if not X.IsEven then Result:= Result + Y;
    if not Result.IsEven then Result:= Result + N;
    Result:= Result shr 1;
    X:= X shr 1;
  end;
  if Result >= N then Result:= Result - N;
end;

function ModExp(B, E, N: BigInteger): BigInteger;
var
  R, MontB: BigInteger;
  I: Integer;

begin
  R:= BigInteger.PowerOfTwo(1024) mod N;
  MontB:= (B * R) mod N;
  for I:= 1023 downto 0 do begin
    R:= MontMult(R, R, N);
    if not (E shr I).IsEven then
      R:= MontMult(MontB, R, N);
  end;
  Result:= MontMult(R, 1, N);
end;

procedure TestMontMult;
var
  Base, Expo, Modulus: BigInteger;
  MontBase, MontExpo: BigInteger;
  X, Y, R: BigInteger;
  Mont: TMont;

begin
// convert to BigInteger
  Base:= BigInteger.Parse(base1);
  Expo:= BigInteger.Parse(exponent1);
  Modulus:= BigInteger.Parse(modulus1);

  R:= BigInteger.PowerOfTwo(1024) mod Modulus;
// Convert into Montgomery form
  MontBase:= (Base * R) mod Modulus;
  MontExpo:= (Expo * R) mod Modulus;
  Writeln;

// MontMult test, all 3 versions output
//  '0x146005377258684F3FFD8D9A70D723BDD3A2E3A160E11B7AD35A7106D4D903AB9D14A9201'+
//  'D0907CE2FC2E04A69656C38CE64AA0BADF2376AEFB19D8732CE2B3650466E31BB78CF24F4E3'+
//  '774A78575738B668DA0E40C8DDDA972CE101E0CADC5D4CCFF6EF2E4E97AF02F34E3AB7258A7'+
//  '323E472FC051825FFC72ADC53B0DAF3C4';
  Writeln('Using MontMult');
  Writeln(MontMult(MontMult(MontBase, MontExpo, Modulus), 1, Modulus).ToHexString);
// same using TMont instance
  Writeln('Using TMont.Multiply');
  Mont:= TMont.GetInstance(Modulus);
  Writeln(Mont.Reduce(Mont.Multiply(MontBase, MontExpo)).ToHexString);
  Writeln('Using TMont.ModMul');
  Writeln(Mont.ModMul(Base,Expo).ToHexString);

// ModExp test, all 3 versions output 29
  Writeln('Using ModExp');
  Writeln(ModExp(Base, Expo, Modulus).ToString);
  Writeln('Using BigInteger.ModPow');
  Writeln(BigInteger.ModPow(Base, Expo, Modulus).ToString);
  Writeln('Using TMont.ModPow');
  Writeln(Mont.ModPow(Base, Expo).ToString);
end;
Источник
Другие вопросы по тегам