Liczby pierwsze - algorytm RSA

System szyfrowania danych RSA
-----------------------------
 (C)2005  mgr Jerzy Wałaszek

MENU
====
[ 0 ] - Koniec pracy programu
[ 1 ] - Generowanie kluczy RSA
[ 2 ] - Kodowanie RSA

Jaki jest twój wybór? (0, 1 lub 2) :

Generowanie kluczy RSA
----------------------

KLUCZ PUBLICZNY
wykładnik e =    3
    moduł n =  391

KLUCZ PRYWATNY
wykładnik d =  235

Zapisz te dane i naciśnij Enter

Kodowanie danych RSA
--------------------

Podaj wykładnik = 3
    Podaj moduł = 391
----------------------------------

Podaj kod RSA   = 123

Wynik kodowania = 98

Zapisz te dane i naciśnij Enter

Kodowanie danych RSA
--------------------

Podaj wykładnik = 235
    Podaj moduł = 391
----------------------------------

Podaj kod RSA   = 98

Wynik kodowania = 123

Zapisz te dane i naciśnij Enter

{
 *******************************************************
 ** Przykładowa aplikacja obrazująca sposób działania **
 ** asymetrycznego systemu kodowania informacji RSA.  **
 ** ------------------------------------------------- **
 **           (C)2003 mgr Jerzy Wałaszek              **
 **            I Liceum Ogólnokształcące              **
 **          im. Kazimierza Brodzińskiego             **
 **                   w Tarnowie                      **
 *******************************************************
}

program rsa;

{$APPTYPE CONSOLE}

// Procedura oczekuje na naciśnięcie klawisza Enter
// po czym czyści ekran okna konsoli
//-------------------------------------------------

procedure Czekaj;
var
  i : integer;
begin
  writeln;
  writeln('Zapisz te dane i nacisnij Enter');
  readln;
  for i := 1 to 500 do writeln;
end;

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------

function nwd(a,b : integer) : integer;
var
  t : integer;
begin
  while b <> 0 do
  begin
    t := b;
    b := a mod b;
    a := t
  end;
  nwd := a
end;

// Funkcja obliczania odwrotności modulo n
//----------------------------------------

function odwr_mod(a,n : integer) : integer;
var
  a0,n0,p0,p1,q,r,t : integer;
begin
  p0 := 0; p1 := 1; a0 := a; n0 := n;
  q  := n0 div a0;
  r  := n0 mod a0;
  while r > 0 do
  begin
    t := p0 - q * p1;
    if t >= 0 then
      t := t mod n
    else
      t := n - ((-t) mod n);
    p0 := p1; p1 := t;
    n0 := a0; a0 := r;
    q  := n0 div a0;
    r  := n0 mod a0;
  end;
  odwr_mod := p1;
end;

// Procedura generowania kluczy RSA
//---------------------------------

procedure klucze_RSA;
const
  tp : array[0..9] of integer =
  (11,13,17,19,23,29,31,37,41,43);
var
  p,q,phi,n,e,d : integer;
begin
  writeln('Generowanie kluczy RSA');
  writeln('----------------------');
  writeln;

// generujemy dwie różne, losowe liczby pierwsze

  repeat
    p := tp[random(10)];
    q := tp[random(10)];
  until p <> q;

  phi := (p - 1) * (q - 1);
  n   := p * q;

// wyznaczamy wykładniki e i d

  e := 3;
  while nwd(e,phi) <> 1 do inc(e,2);
  d := odwr_mod(e,phi);

// gotowe, wypisujemy klucze

  writeln('KLUCZ PUBLICZNY');
  writeln('wykladnik e = ',e);
  writeln('    modul n = ',n);
  writeln;
  writeln('KLUCZ PRYWATNY');
  writeln('wykladnik d = ',d);
  Czekaj;
end;

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------

function pot_mod(a,w,n : integer) : integer;
var
  pot,wyn,q  : integer;
begin

// wykładnik w rozbieramy na sumę potęg 2. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.

  pot := a; wyn := 1; q := w;
  while q > 0 do
  begin
    if (q mod 2) = 1 then wyn := (wyn * pot) mod n;
    pot := (pot * pot) mod n; // kolejna potęga
    q := q div 2;
  end;
  pot_mod := wyn;
end;

// Procedura kodowania danych RSA
//-------------------------------

procedure kodowanie_RSA;
var
  e,n,t : integer;
begin
  writeln('Kodowanie danych RSA');
  writeln('--------------------');
  writeln;
  write('Podaj wykladnik = '); readln(e);
  write('    Podaj modul = '); readln(n);
  writeln('----------------------------------');
  writeln;
  write('Podaj kod RSA   = '); readln(t);
  writeln;
  writeln('Wynik kodowania = ',pot_mod(t,e,n));
  Czekaj;
end;

// ********************
// ** Program główny **
// ********************

var
  w : integer;

begin
  randomize;
  repeat
    writeln('System szyfrowania danych RSA');
    writeln('-----------------------------');
    writeln(' (C)2003  mgr Jerzy Walaszek ');
    writeln;
    writeln('MENU');
    writeln('====');
    writeln('[ 0 ] - Koniec pracy programu');
    writeln('[ 1 ] - Generowanie kluczy RSA');
    writeln('[ 2 ] - Kodowanie RSA');
    writeln;
    write('Jaki jest twoj wybor? (0, 1 lub 2) : ');
    readln(w);
    writeln; writeln; writeln;
    case w of
      1 : klucze_RSA;
      2 : kodowanie_RSA;
    end;
    writeln; writeln; writeln;
  until w = 0;
end.

/*
 *******************************************************
 ** Przykładowa aplikacja obrazująca sposób działania **
 ** asymetrycznego systemu kodowania informacji RSA.  **
 ** ------------------------------------------------- **
 **           (C)2003 mgr Jerzy Wałaszek              **
 **            I Liceum Ogólnokształcące              **
 **          im. Kazimierza Brodzińskiego             **
 **                   w Tarnowie                      **
 *******************************************************
*/

#include <iostream>
#include <iomanip>

using namespace std;

// Funkcja czeka na dowolny klawisz i czyści ekran
//------------------------------------------------

void czekaj(void)
{
  char c[1];

  cout << "\nZapisz te dane\n\n";
  cin.getline(c,1);
  cin.getline(c,1);	
  for(int i = 1; i < 500; i++) cout << endl;

}

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------

int nwd(int a, int b)
{
  int t;

  while(b != 0)
  {
    t = b;
    b = a % b;
    a = t;
  };
  return a;
}

// Funkcja obliczania odwrotności modulo n
//----------------------------------------

int odwr_mod(int a, int n)
{
  int a0,n0,p0,p1,q,r,t;

  p0 = 0; p1 = 1; a0 = a; n0 = n;
  q  = n0 / a0;
  r  = n0 % a0;
  while(r > 0)
  {
    t = p0 - q * p1;
    if(t >= 0)
      t = t % n;
    else
      t = n - ((-t) % n);
    p0 = p1; p1 = t;
    n0 = a0; a0 = r;
    q  = n0 / a0;
    r  = n0 % a0;
  }
  return p1;
}

// Procedura generowania kluczy RSA
//---------------------------------

void klucze_RSA()
{
  const int tp[10] = {11,13,17,19,23,29,31,37,41,43};
  int p,q,phi,n,e,d;

  cout << "Generowanie kluczy RSA\n"
          "----------------------\n\n";

// generujemy dwie różne, losowe liczby pierwsze

  do
  {
    p = tp[rand() % 10];
    q = tp[rand() % 10];
  } while (p == q);

  phi = (p - 1) * (q - 1);
  n   = p * q;

// wyznaczamy wykładniki e i d

  for(e = 3; nwd(e,phi) != 1; e += 2);
  d = odwr_mod(e,phi);

// gotowe, wypisujemy klucze

  cout << "KLUCZ PUBLICZNY\n"
          "wykladnik e = " << e
       << "\n    modul n = " << n
       << "\n\nKLUCZ PRYWATNY\n"
          "wykladnik d = " << d << endl;
  czekaj();
}

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------

int pot_mod(int a, int w, int n)
{
  int pot,wyn,q;

// wykładnik w rozbieramy na sumę potęg 2
// przy pomocy algorytmu Hornera. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.

  pot = a; wyn = 1;
  for(q = w; q > 0; q /= 2)
  {
    if(q % 2) wyn = (wyn * pot) % n;
    pot = (pot * pot) % n; // kolejna potęga
  }
  return wyn;
}

// Procedura kodowania danych RSA
//-------------------------------

void kodowanie_RSA()
{
  int e,n,t;

  cout << "Kodowanie danych RSA\n"
          "--------------------\n\n"
          "Podaj wykladnik = "; cin  >> e;
  cout << "    Podaj modul = "; cin  >> n;
  cout << "----------------------------------\n\n"
          "Podaj kod RSA   = "; cin  >> t;
  cout << "\nWynik kodowania = " << pot_mod(t,e,n) << endl;

  czekaj();
}

// ********************
// ** Program główny **
// ********************

main()
{
  int w;

  srand((unsigned)time(NULL));

  do
  {
    cout << "System szyfrowania danych RSA\n"
            "-----------------------------\n"
            " (C)2003  mgr Jerzy Walaszek\n\n"
            "MENU\n"
            "====\n"
            "[ 0 ] - Koniec pracy programu\n"
            "[ 1 ] - Generowanie kluczy RSA\n"
            "[ 2 ] - Kodowanie RSA\n\n"
            "Jaki jest twoj wybor? (0, 1 lub 2) : ";
    cin  >> w;
    cout << "\n\n\n";
    switch (w)
    {  
      case 1 : klucze_RSA(); break;
      case 2 : kodowanie_RSA(); break;
    }
    cout << "\n\n\n";
  } while(w != 0);
}

' *******************************************************
' ** Przykładowa aplikacja obrazująca sposób działania **
' ** asymetrycznego systemu kodowania informacji RSA.  **
' ** ------------------------------------------------- **
' **           (C)2005 mgr Jerzy Wałaszek              **
' **            I Liceum Ogólnokształcące              **
' **          im. Kazimierza Brodzińskiego             **
' **                   w Tarnowie                      **
' *******************************************************

Option Explicit On

Module Module1

  ' Procedura oczekuje na naciśnięcie klawisza Enter
  ' po czym czyści ekran okna konsoli
  '-------------------------------------------------

  Public Sub Czekaj()

    Console.WriteLine()
    Console.WriteLine("Zapisz te dane i naciśnij Enter")
    Console.ReadLine()

  End Sub

  ' Funkcja obliczająca NWD dla dwóch liczb
  '----------------------------------------

  Public Function nwd(ByVal a As Integer, ByVal b As Integer) As Integer

    Dim t As Integer

    While b <> 0
      t = b
      b = a Mod b
      a = t
    End While
    Return a

  End Function

  ' Funkcja obliczania odwrotności modulo n
  '----------------------------------------

  Public Function odwr_mod(ByVal a As Integer, ByVal n As Integer) As Integer

    Dim a0, n0, p0, p1, q, r, t As Integer

    p0 = 0 : p1 = 1 : a0 = a : n0 = n
    q = n0 \ a0
    r = n0 Mod a0
    While r > 0
      t = p0 - q * p1
      If t >= 0 Then
        t = t Mod n
      Else
        t = n - ((-t) Mod n)
      End If
      p0 = p1 : p1 = t
      n0 = a0 : a0 = r
      q = n0 \ a0
      r = n0 Mod a0
    End While
    Return p1

  End Function

  ' Procedura generowania kluczy RSA
  '---------------------------------

  Public Sub klucze_RSA()

    Dim tp() As Integer = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43}
    Dim p, q, phi, n, e, d As Integer

    Console.Clear()
    Console.WriteLine("Generowanie kluczy RSA")
    Console.WriteLine("----------------------")
    Console.WriteLine()

    ' generujemy dwie różne, losowe liczby pierwsze

    Do
      p = tp(Int(Rnd() * 10))
      q = tp(Int(Rnd() * 10))
    Loop Until p <> q

    phi = (p - 1) * (q - 1)
    n = p * q

    ' wyznaczamy wykładniki e i d

    e = 3
    While nwd(e, phi) <> 1 : e = e + 2 : End While
    d = odwr_mod(e, phi)

    ' gotowe, wypisujemy klucze

    Console.WriteLine("KLUCZ PUBLICZNY")
    Console.WriteLine("wykładnik e = {0,4}", e)
    Console.WriteLine("    moduł n = {0,4}", n)
    Console.WriteLine()
    Console.WriteLine("KLUCZ PRYWATNY")
    Console.WriteLine("wykładnik d = {0,4}", d)
    Czekaj()

  End Sub

  ' Funkcja oblicza modulo potęgę podanej liczby
  '---------------------------------------------

  Public Function pot_mod(ByVal a As Integer, ByVal w As Integer, _
                          ByVal n As Integer) As Integer

    Dim pot, wyn, q As Integer

    ' wykładnik w rozbieramy na sumę potęg 2. Dla reszt
    ' niezerowych tworzymy iloczyn potęg a modulo n.

    pot = a : wyn = 1 : q = w
    While q > 0
      If (q Mod 2) = 1 Then wyn = (wyn * pot) Mod n
      pot = (pot * pot) Mod n  ' kolejna potęga
      q = q \ 2
    End While
    Return wyn

  End Function

  ' Procedura kodowania danych RSA
  '-------------------------------

  Public Sub kodowanie_RSA()

    Dim e, n, t As Integer

    Console.Clear()
    Console.WriteLine("Kodowanie danych RSA")
    Console.WriteLine("--------------------")
    Console.WriteLine()
    Console.Write("Podaj wykładnik = ") : e = Val(Console.ReadLine)
    Console.Write("    Podaj moduł = ") : n = Val(Console.ReadLine)
    Console.WriteLine("----------------------------------")
    Console.WriteLine()
    Console.Write("Podaj kod RSA   = ") : t = Val(Console.ReadLine)
    Console.WriteLine()
    Console.WriteLine("Wynik kodowania = {0}", pot_mod(t, e, n))
    Czekaj()

  End Sub

  Sub main()

    Dim w As Integer

    Randomize()
    Do
      Console.Clear()
      Console.WriteLine("System szyfrowania danych RSA")
      Console.WriteLine("-----------------------------")
      Console.WriteLine(" (C)2005  mgr Jerzy Wałaszek ")
      Console.WriteLine()
      Console.WriteLine("MENU")
      Console.WriteLine("====")
      Console.WriteLine("[ 0 ] - Koniec pracy programu")
      Console.WriteLine("[ 1 ] - Generowanie kluczy RSA")
      Console.WriteLine("[ 2 ] - Kodowanie RSA")
      Console.WriteLine()
      Console.Write("Jaki jest twój wybór? (0, 1 lub 2) : ")
      w = Val(Console.ReadLine)
      Select Case w
        Case 1 : klucze_RSA()
        Case 2 : kodowanie_RSA()
      End Select
    Loop Until w = 0

  End Sub

End Module

Program należy uruchamiać z dysku przez podwójne kliknięcie myszką pliku ze skryptem.

# -*- coding: cp1250 -*-
# *******************************************************
# ** Przykładowa aplikacja obrazująca sposób działania **
# ** asymetrycznego systemu kodowania informacji RSA.  **
# ** ------------------------------------------------- **
# **           (C)2005 mgr Jerzy Wałaszek              **
# **            I Liceum Ogólnokształcące              **
# **          im. Kazimierza Brodzińskiego             **
# **                   w Tarnowie                      **
# *******************************************************

import random
import os

# Procedura wywołuje polecenie systemowe, które czyści
# zawartość okienka konsoli znakowej. W systemie Windows
# jest to cls. W systemie Unix clear
#-------------------------------------------------------
def cls():
  os.system("cls")
  
# Procedura oczekuje na naciśnięcie klawisza Enter
# po czym czyści ekran okna konsoli
#-------------------------------------------------

def Czekaj():
  print
  raw_input("Zapisz te dane i nacisnij Enter")

# Funkcja obliczająca NWD dla dwóch liczb
#----------------------------------------

def nwd(a, b):
  while b: a, b = b, a % b
  return a

# Funkcja obliczania odwrotności modulo n
#----------------------------------------

def odwr_mod(a, n):
  p0, p1, a0, n0 = 0, 1, a, n
  q, r = n0 // a0, n0 % a0
  while r:
    t = p0 - q * p1
    if t >= 0:
      t = t % n
    else:
      t = n - ((-t) % n)
    p0, p1, n0, a0 = p1, t, a0, r
    q, r  = n0 // a0, n0 % a0
  return p1

# Procedura generowania kluczy RSA
#---------------------------------

def klucze_RSA():
  tp = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
  cls()
  print "Generowanie kluczy RSA"
  print "----------------------"
  print

# generujemy dwie różne, losowe liczby pierwsze

  p = q = 0
  while p == q:
    p, q = tp[random.randint(0, 9)], tp[random.randint(0, 9)]
  phi, n = (p - 1) * (q - 1), p * q

# wyznaczamy wykładniki e i d

  e = 3
  while nwd(e, phi) != 1: e += 2
  d = odwr_mod(e, phi)

# gotowe, wypisujemy klucze

  print "KLUCZ PUBLICZNY"
  print "wykladnik e = %4d" % e
  print "    modul n = %4d" % n
  print
  print "KLUCZ PRYWATNY"
  print "wykladnik d = %4d" % d
  Czekaj()

# Funkcja oblicza modulo potęgę podanej liczby
#---------------------------------------------

def pot_mod(a, w, n):

# wykładnik w rozbieramy na sumę potęg 2. Dla reszt
# niezerowych tworzymy iloczyn potęg a modulo n.

  pot, wyn, q = a, 1, w
  while q:
    if (q % 2) == 1: wyn = (wyn * pot) % n
    pot = (pot * pot) % n # kolejna potęga
    q //= 2
  return wyn

# Procedura kodowania danych RSA
#-------------------------------

def kodowanie_RSA():
  cls()
  print "Kodowanie danych RSA"
  print "--------------------"
  print
  e = int(raw_input("Podaj wykladnik = "))
  n = int(raw_input("    Podaj modul = "))
  print "----------------------------------"
  print
  t = int(raw_input("Podaj kod RSA   = "))
  print
  print "Wynik kodowania =", pot_mod(t, e, n)
  Czekaj()

# ********************
# ** Program główny **
# ********************

w = 1
while w:
  cls()
  print "System szyfrowania danych RSA"
  print "-----------------------------"
  print " (C)2005  mgr Jerzy Walaszek "
  print
  print "MENU"
  print "===="
  print "[ 0 ] - Koniec pracy programu"
  print "[ 1 ] - Generowanie kluczy RSA"
  print "[ 2 ] - Kodowanie RSA"
  print
  w = int(raw_input("Jaki jest twoj wybor? (0, 1 lub 2) : "))
  if   w == 1: klucze_RSA()
  elif w == 2: kodowanie_RSA()

<html>
<head>
  <title>Algorytm RSA</title>
</head>
<body>
  <form style="border:2px outset #FFCC00;
               PADDING-RIGHT: 4px;
               PADDING-LEFT: 4px;
               PADDING-BOTTOM: 1px;
               PADDING-TOP: 1px;
               BACKGROUND-COLOR: #FFCC00"
        name="rsa">
    <div align="center"><center>
      <h2>Generator kluczy RSA</h2>
      <p>(C)2004 mgr Jerzy Wałaszek I LO w Tarnowie</p>
      <p>
<input onclick="js_genkeys()" type="button" value="Generuj klucze">
<input onclick="js_keyclr()" type="button" value="Czyść klucze">
      </p>
      <table cellSpacing="4" cellPadding="4"
             bgColor="#FF9933" border="0"
             style="border-collapse: collapse">
        <tr>
          <th colSpan="2">Klucz publiczny</th>
          <th colSpan="2">Klucz prywatny</th>
        </tr>
        <tr>
          <td>wykładnik</td>
          <td id="gkey_e" style="TEXT-ALIGN: center">...</td>
          <td>wykładnik</td>
          <td id="gkey_d" style="TEXT-ALIGN: center">...</td>
        </tr>
        <tr>
          <td>moduł</td>
          <td id="gkey_n1" style="TEXT-ALIGN: center">...</td>
          <td>moduł</td>
          <td id="gkey_n2" style="TEXT-ALIGN: center">...</td>
        </tr>
      </table>
      <hr>
      <h2>Koder szyfru RSA</h2>
      <p>(C)2004 mgr Jerzy Wałaszek I LO w Tarnowie</p>
      <table cellSpacing="4"
             cellPadding="4"
             bgColor="#FF9933"
             border="0"
             style="border-collapse: collapse">
        <tr>
          <td>wykładnik</td>
          <td><input name="ed"></td>
        </tr>
        <tr>
          <td>moduł</td>
          <td><input name="n"></td>
        </tr>
        <tr>
          <td>wiadomość</td>
          <td><input name="m"></td>
        </tr>
      </table>
      <p>
<input onclick="js_codeRSA()" type="button" value="Koduj RSA">
<input onclick="js_codeclr()" type="button" value="Czyść formularz">
      </p>
      <p id="rsa_out">...</p>
    </center></div>
  </form>

<script language="JavaScript">

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------

function nwd(a, b)
{
  var t;

  while(b != 0)
  {
    t = b; b = a % b; a = t;
  }
  return a;
}

// Funkcja obliczania odwrotności modulo n
//----------------------------------------

function odwr_mod(a, n)
{
  var a0,n0,p0,p1,q,r,t;

  p0 = 0; p1 = 1; a0 = a; n0 = n;
  q = Math.floor(n0 / a0);
  r = n0 % a0;
  while(r > 0)
  {
    t = p0 - q * p1;
    if(t >= 0) t = t % n; else t = n - ((-t) % n);
    p0 = p1; p1 = t;
    n0 = a0; a0 = r;
    q = Math.floor(n0 / a0);
    r = n0 % a0;
  }
  return p1;
}

function js_genkeys()
{
  var tp = new Array(11,13,17,19,23,29,31,37,41,43);
  var p,q,phi,n,e,d;

// generujemy dwie różne, losowe liczby pierwsze

  do
  {
    p = tp[Math.floor(Math.random() * 10)];
    q = tp[Math.floor(Math.random() * 10)];
  }while (p == q);

  phi = (p - 1) * (q - 1); n = p * q;

// wyznaczamy wykładniki e i d

  for(e = 3; nwd(e,phi) != 1; e += 2);
  d = odwr_mod(e,phi);

// gotowe, wypisujemy klucze

  document.getElementById("gkey_e").innerHTML = e;
  document.getElementById("gkey_d").innerHTML = d;
  document.getElementById("gkey_n1").innerHTML = n;
  document.getElementById("gkey_n2").innerHTML = n;
}

function js_keyclr()
{
  document.getElementById("gkey_e").innerHTML = " ";
  document.getElementById("gkey_d").innerHTML = " ";
  document.getElementById("gkey_n1").innerHTML = " ";
  document.getElementById("gkey_n2").innerHTML = " ";
}

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------

function pot_mod(a, w, n)
{
  var pot,wyn,q;

// wykładnik w rozbieramy na sumę potęg 2. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.

  pot = a; wyn = 1;
  for(q = w; q > 0; q = Math.floor(q / 2))
  {
    if(q % 2) wyn = (wyn * pot) % n;
    pot = (pot * pot) % n; // kolejna potęga
  }
  return wyn;
}

function js_codeRSA()
{
  var e,n,t,s;

  e = parseInt(document.rsa.ed.value);
  n = parseInt(document.rsa.n.value);
  t = parseInt(document.rsa.m.value);
  if(isNaN(e) || isNaN(n) || isNaN(t))
    s = "Błąd danych";
  else
    s = pot_mod(t,e,n);
  document.getElementById("rsa_out").innerHTML = s;
}

function js_codeclr()
{
  document.rsa.ed.value = "";
  document.rsa.n.value = "";
  document.rsa.m.value = "";
  document.getElementById("rsa_out").innerHTML = " ";
}
</script>
</body>
</html>