Обработка переполнения при работе с большими числами в Delphi: пример решения проблемы с EIntOverflow

Delphi , Синтаксис , Типы и Переменные

Введение

При работе с большими числами в Delphi, особенно при реализации криптографических алгоритмов, таких как RSA, разработчики часто сталкиваются с проблемой переполнения целочисленных типов. В данной статье мы рассмотрим конкретный случай, описанный на форуме, где возникала ошибка EIntOverflow при использовании библиотеки BigNumbers от Rudy Velthuis, и предложим несколько подходов к решению этой проблемы.

Проблема переполнения в BigNumbers

Как описывает пользователь pmcgee, при генерации больших простых чисел и выполнении арифметических операций с ними в Delphi 10.3.3 и более новых версиях (11.3, 12.3) возникала ошибка EIntOverflow. Проблема проявлялась в следующем коде:

const
  CMultiplier = UInt64(6364136223846793005);
  CIncrement = UInt64(1442695040888963407);

begin
{$IFOPT Q+}
{$DEFINE HasRangeChecks}
{$ENDIF}
  FSeed := Int64(FSeed * CMultiplier + CIncrement); // << EIntOverflow
  Result := UInt32(FSeed shr (64 - Bits));
{$IFDEF HasRangeChecks}
{$RANGECHECKS ON}
{$ENDIF}
end;

Анализ проблемы

Основная проблема заключается в том, что при умножении двух 64-битных чисел (FSeed и CMultiplier) может произойти переполнение, даже если результат затем приводится к Int64. Delphi по умолчанию включает проверку переполнения (Overflow checking), что приводит к возникновению исключения EIntOverflow.

Решение 1: Отключение проверки переполнения

Первый и самый простой способ решения - отключить проверку переполнения для конкретного участка кода:

function TRandom.Next(Bits: Integer): UInt32;
begin
{$IFOPT R+}
{$DEFINE HasRangeChecks}
{$ENDIF}
{$IFOPT Q+}
{$DEFINE HasOverflowChecks}
{$ENDIF}
{$RANGECHECKS OFF}
{$OVERFLOWCHECKS OFF}
  FSeed := (FSeed * CMultiplier + CIncrement);
  Result := UInt32(FSeed shr (64 - Bits));
{$IFDEF HasRangeChecks}
{$RANGECHECKS ON}
{$ENDIF}
{$IFDEF HasOverflowChecks}
{$OVERFLOWCHECKS ON}
{$ENDIF}
end;

Важно отметить, что в оригинальном коде были перепутаны директивы: использовалась Q+ для проверки диапазона (Range checks), тогда как на самом деле Q+ отвечает за проверку переполнения (Overflow checks).

Решение 2: Разделение операции на части

Альтернативный подход, который изначально использовал pmcgee, заключается в разбиении операции умножения на части, чтобы избежать переполнения:

// (A.e32 + B) * (C.e32 + D) = AC.e64 + (AD+BC).e32 + BD
var
  A, B, C, D, BD, ADBC, f1, f2: UInt64;
begin
  A := FSeed shr 32;          // верхние 32 бита
  C := CMultiplier shr 32;
  B := FSeed and $FFFFFFFF;   // нижние 32 бита
  D := CMultiplier and $FFFFFFFF;
  BD := B * D;
  ADBC := A * D + B * C;

  f1 := BD + CIncrement;
  f2 := ADBC shl 32;
  F := (f1 and $0FFFFFFFFFFFFFFF) + (f2 and $0FFFFFFFFFFFFFFF);

  FSeed := Int64(F);
end;

Этот метод аналогичен алгоритму Карацубы для умножения больших чисел, где операция разбивается на несколько меньших умножений.

Решение 3: Использование беззнаковых типов

Как отметил Kas Ob., основная проблема может быть связана с использованием знакового типа Int64 вместо беззнакового UInt64. Линейный конгруэнтный генератор (LCG), используемый в коде, по определению работает с беззнаковыми числами:

// Изменение типа FSeed с Int64 на UInt64
FSeed: UInt64;

// И соответствующие константы
const
  CMultiplier: UInt64 = 6364136223846793005;
  CIncrement: UInt64 = 1442695040888963407;

Дополнительные исправления

В ходе обсуждения были выявлены и другие места в коде, где требуется исправление:

1. В методе TRandomBase.NextBytes переменная Rnd должна быть объявлена как UInt32 вместо Integer:

procedure TRandomBase.NextBytes(var Bytes: array of Byte);
var
  Head, Tail: Integer;
  N, I: Integer;
  Rnd: UInt32; // исправлено с Integer на UInt32
begin
  // ... остальной код
end;

Криптографические аспекты

Важно отметить, что используемый в библиотеке генератор псевдослучайных чисел (LCG) не является криптографически стойким. Как отметил Kas Ob., для криптографических целей, таких как генерация ключей RSA, следует использовать криптографически стойкие генераторы, например, ChaCha8 или ChaCha20.

Пример реализации RSA на Delphi

Для полноты картины приведем простой пример генерации ключей RSA с использованием исправленной версии BigNumbers:

procedure GenerateRSAKeys(var PublicKey, PrivateKey: TBigInteger; BitLength: Integer);
var
  p, q, n, phi, e, d: TBigInteger;
  Rand: IRandom;
begin
  // Создаем криптографически стойкий генератор случайных чисел
  // В реальной реализации используйте надежный CSPRNG!
  Rand := TRandom.Create(GetTickCount);

  // Генерируем два больших простых числа
  p := TBigInteger.CreateProbablePrime(BitLength div 2, Rand);
  q := TBigInteger.CreateProbablePrime(BitLength div 2, Rand);

  // Вычисляем модуль
  n := p * q;

  // Вычисляем функцию Эйлера
  phi := (p - 1) * (q - 1);

  // Выбираем открытую экспоненту (обычно 65537)
  e := TBigInteger.Create(65537);

  // Вычисляем секретную экспоненту
  d := e.ModInverse(phi);

  // Возвращаем ключи
  PublicKey := TBigInteger.Create(n.ToByteArray + e.ToByteArray);
  PrivateKey := TBigInteger.Create(n.ToByteArray + d.ToByteArray);
end;

Заключение

Проблема переполнения при работе с большими числами в Delphi может быть решена несколькими способами:
1. Отключением проверки переполнения для конкретных участков кода
2. Разделением операций на части
3. Использованием беззнаковых типов данных

Для криптографических приложений важно не только правильно обрабатывать большие числа, но и использовать криптографически стойкие алгоритмы генерации случайных чисел. Библиотека BigNumbers предоставляет хорошую основу для работы с большими числами, но требует внимания к деталям реализации, особенно в новых версиях Delphi.

Как показало обсуждение, совместная работа сообщества помогает быстро выявлять и исправлять подобные проблемы, что делает open-source решения более надежными и устойчивыми к ошибкам.

Создано по материалам из источника по ссылке.

Статья описывает методы решения проблемы переполнения при работе с большими числами в Delphi, включая отключение проверки переполнения, разделение операций и использование беззнаковых типов.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Типы и Переменные ::