Archive SkazOff Blog

ЭЦП RSA

Перебирая архивы за прошлые годы нашел задание с 4ого кажется курса — реализация ЭЦП (RSA), выложу исходники, возможно кому-нибудь пригодится. Делал на дельфях.

Изначально судя по документам задание звучало так: «Разработать алгоритм электронной цифровой подписи на основе алгоритма. RSA. Создать подделку цифровой подписи. Проверить подлинность исходной цифровой подписи и подделки. Сделать выводы о безопасности цифровой подписи открытого текста и его целостности.»

Ну для начала что такое RSA можно почитать в википедии. Про ЭЦП на основе RSA есть тут и тут, по последней ссылке есть даже реализация, точнее фрагменты кода. Форма выглядит вот так. Последовательность действий думаю ясна:

1.Генерируем ключи (+делаем вывод различных переменных типа p и q, для наглядности»)

2.Вводим текст и подписываем его

3.Передаем текст

4.Проверяем текст.

 
Функция вычисления s=x^e mod n:

function PowerInMod(base, ex, modul: uint64): uint64;     
  begin
    if ex = 0 then result := 1
    else
    begin
      if ex = 1 then result := base
      else
      begin
        result := PowerInMod(base, ex div 2, modul);
        result := result * result mod modul;
        if (ex mod 2) <> 0 then result := result * base mod modul;
      end;
    end;
  end;

Получаем случайное простое число:

  function GetSimpleNumber: uint64;    
  var ok: boolean;
    i: uint64;
  begin
    ok := false;
    while not ok do
    begin
      result := random(Max) + 3;
      i := 2;
      while i <= result do
      begin
        if (result mod i) = 0 then break;
        inc(i);
      end;
      if i = result then ok := true;
    end;
  end;

Расширенный алгоритм Евклида:

function gcd_ext(a, b: int64): int64;      
  var a0, x_, v_, y_, u_, q_, r_, newu_, newv_: int64;
  begin
    a0 := a;
    x_ := 1;
    v_ := 1;
    y_ := 0;
    u_ := 0;
    while b <> 0 do
    begin
      q_ := a div b;
      r_ := a mod b;
      a := b;
      b := r_;
      newu_ := x_ - q_ * u_;
      newv_ := y_ - q_ * v_;
      x_ := u_;
      y_ := v_;
      u_ := newu_;
      v_ := newv_;
    end;
    if y_ > 0 then result := y_
    else result := y_ + a0;
  end;

NOD:

function gcd(a, b: uint64): uint64;      
  begin
    repeat
      if a > b then a := a mod b
      else b := b mod a;
    until (a = 0) or (b = 0);
    result := a + b;
  end;

Два числа взаимно простые - когда их НОД=1:

  function SimpleBetween(ValueN: uint): uint;
  var ok: boolean;
    i: int64;
  begin
    ok := false;
    i := 3;
    while not ok do
    begin
      result := i;
      inc(i);
      if gcd(result, ValueN) = 1 then ok := true;
    end;
  end;

Все расчеты:

var x, gcdval: uint64;
begin
  Memo1.Clear;
  randomize;
  //p
  p := GetSimpleNumber;
  //q
  repeat
    q := GetSimpleNumber;
  until p <> q;
  Memo1.Lines.Add('p=' + IntToStr(p));
  Memo1.Lines.Add('q=' + IntToStr(q));
  //n
  n := p * q;
  Memo1.Lines.Add('n=' + IntToStr(n));
  //fi
  fi := (p - 1) * (q - 1);
  Memo1.Lines.Add('(p-1)(q-1)=' + IntToStr(fi));
  //e
  e := SimpleBetween(fi);
  Memo1.Lines.Add('e=' + IntToStr(e));
  //расширенный алгоритм евклида
  d := gcd_ext(fi, e);
  Memo1.Lines.Add('d=' + IntToStr(d));
  if gcd(d, n) <> 1 then
  begin
    ShowMessage('d и n получились не взаимно простыми - повторите генерацию');
   { x := PowerInMod(666, e, n);
    if PowerInMod(x, d, n) = 666 then
    begin
      ShowMessage('прокатило')
    end;
    }
  end
end;

Подписываем:

var t,source:string;
    i:integer;
    res:uint64;
begin
  source := Edit1.Text;
  t:='';
  for i:=1 to length(source) do
  begin
    res := PowerInMod( Ord(source[i]) ,d,n);
    t:=t+','+IntToStr(res);
  end;
  delete(t,1,1);
  Edit3.Text := t;
end;

Проверяем подпись:

var t,source:string;
    i:integer;
    res:uint64;
    sl:TStringList;
begin
  sl := TStringList.Create;
  sl.CommaText := Edit3.Text;
  t:='';
  for i:=0 to sl.Count-1 do
  begin
    t := t + Chr(  PowerInMod( StrToInt(sl[i]) ,e,n )  );
  end;
  if t = Edit2.Text then ShowMessage('Подпись верна!')
  else ShowMessage('Подпись НЕверна!')
end;

Вот собственно и все:)