RSA i algorytm Shora

Dodatkowe zrodla informacji

Ćwiczenia:

  • Zadanie 1 Zaimplementowac w dowolnym języku prosty program wyliczajacy kolejne reszty funkcji b^x mod N dla b=4, N=55 dla x od 1 do 100.
    Aby uniknąć przekroczenia zakresu, skorzystac z faktu, ze (a*b) mod N = ((a mod N)*(b mod N)) mod N . Mozna tez wykorzystac implementacje w C#. Zaobserwować okres. Czy łatwo znaleźć go na komputerze klasycznym ?

  • Zadanie 2 Użyj kodu z przykladu poniżej, aby w pętli wyliczyc kolejne wartosci reszt dla x z przedzialu 1..100. Wykonaj kod w symulatorze (Run in Console).
    W symulatorze mamy do dyspozycji zaimplentowana funkcje expModulo. Ta funkcja jest tez dostępna jako złożona bramka obliczeniowa (Select Composite Gate).
    Fragment kodu dla symulatora ilustrujacy uzycie funkcji: a^x mod N: 
           //wczesniej nalezy zadeklarowac i zainicjalizowac x, N, a
       //int N= ...
       //int a= ...
       //ulong x 
      // obliczamy ile bitow potrzeba na zapamiętanie N
	ulong ulongN = (ulong)N;
	int width = (int)Math.Ceiling(Math.Log(N, 2));
 
	// inicjalizujemy komputer kwantowy 		
	QuantumComputer comp = QuantumComputer.GetInstance();
			
 	//inicjalizujemy rejestr wejsciowy 
	Register regX = comp.NewRegister(0, 2 * width);
			
	// inicjalizujemy rejestr wyjsciowy 
	Register regY = comp.NewRegister(1, width + 1);
        
	// ustawiamy wartosc rejestru wejsciowego na x 
	regX.Reset(x);

	// ustawiamy wartosc rejestru wyjsciowego na 1
        // potrzebne, gdy wywolujemy w petli 
	regY.Reset(1);

        // obliczamy a^x mod N
 	comp.ExpModulo(regX, regY, a, N);

        //mierzymy wartosc
 	int valueMeasured = (int)regY.Measure();

        Console.WriteLine ("Dla {0} reszta to {1}",x, valueMeasured);
  • Funkcja emulująca kwantowe znajdowanie okresu funkcji a^x mod N korzysta z podanej powyżej funkcji ExpModulo, którą stosuje na superpozycji wszystkich x o jednakowych amplitudach.
    • Wygeneruj obwod funkcji FindPeriod(int N, int a) w symulatorze. Wykonaj ją i zaobsewuj zmieniajace się wartości w rejestrach. Wykonaj kod w konsoli (Run in Console). Uwaga: istnieje niezerowe prawdopodobieństwo, że znaleziony okres jest zły - należy wtedy powtorzyć obliczenia.

  • Zadanie 3 Użyj w/w funkcji do emulacji algorytmu łamiacego RSA poprzez rozkład N na czynniki p i q (oznaczenia jak w zadaniu domowym). Wynik przedstaw uzywajac opcji symulatora "Run in Console".
    1. rozkładamy N na p i q, tak jak opisano to w sekcji H rozdzialu 3
    2. znajdujemy d czyli odwrotność modulo do c w G_(p-1)(q-1)
    3. obliczamy a=b^d (mod N)

  • Zadanie 4 Użyj w/w plików do emulacji algorytmu "Ewy".
    Uwaga: to działa dla b względnie pierwszych z N (czyli prawie zawsze dla dużych N). W przypadku, gdyby b miało wspolny dzielnik z N wiekszy niz 1, to nalezy zastosowac algorytm Euklidesa.
    1. znajdz r - okres b^x mod N
    2. policz d’ - odwrotność modulo c w G_r,
    3. policz a=b^d’ (mod N)
  • Uwaga: potrzebne bedą funkcje pomocnicze:
    1. algorytm NWD Euklidesa (można skorzystać z implementacji w C#)
    2. znajdowanie odwrotności modulo (mozna użyć rozszerzonego algorytmu Euklidesa, albo zaimplemntować "wprost").
    3. algorytm potęgowania korzystajacy z rozwinięcia dwójkowego wykładnika tak jak w p. a) zadania domowego. Kwantowy aspekt tej metody jest opisany w sekcji F (w implementacji można stosować klasyczne rozwiązanie). Mozna wykorzystac implementacje w C#
  • Dla zadań 3 i 4 przetestuj swoją implementacje dla wybranych a, N=p*q (p,q - pierwsze) oraz c. Pamietaj, ze c nie moze miec wspólnych podzielników z (p-1)*(q-1).
  • Zalizenie części praktycznej polega na demonstracji wyników zadań 1-4.

Zadanie domowe (na nastepne lab):