Teoria gry

Teoria gier jest z pewnością dość starym pojęciem i jest wykorzystywana w wielu rzeczywistych sytuacjach do rozwiązywania złożonych problemów. Powodem, dla którego omawiamy ten temat na wysokim poziomie, jest to, że jest on używany w Bitcoinach i wielu innych rozwiązaniach blockchain. Został formalnie wprowadzony przez Johna von Neumanna do badania decyzji gospodarczych. Później został bardziej spopularyzowany przez Johna Forbesa Nasha Jr ze względu na jego teorię „Nash Equilibrium”, którą przyjrzymy się wkrótce. Najpierw zrozumiemy, czym jest teoria gier. Teoria gier jest teorią gier, w której gry nie są tylko tym, czym bawią się dzieci. Większość z nich to sytuacje, w których dwie lub więcej stron jest zaangażowanych w pewne strategiczne zachowania. Przykłady: turniej krykieta to gra, dwie sprzeczne strony w sądzie z prawnikami i ławami przysięgłych to gra, dwoje rodzeństwa walczącego o lody to gra, wybory polityczne to gra, sygnał drogowy to także gra . Inny przykład: powiedzmy, że złożyłeś wniosek o pracę w Blockchain, a zostałeś wybrany i zaoferowałeś ofertę pracy z pewnym wynagrodzeniem, ale odrzucasz ofertę, myśląc, że istnieje ogromna luka w popycie i podaży, a szanse są dobre, że zmienią ofertę z wyższa pensja. Musisz teraz myśleć, co nie jest grą? Cóż, w rzeczywistych sytuacjach prawie wszystko jest grą. Tak więc „grę” można zdefiniować jako sytuację obejmującą „skorelowany wybór racjonalny”. Oznacza to, że perspektywy dostępne dla każdego gracza zależą nie tylko od własnych wyborów, ale także od wyborów dokonywanych przez innych w danej sytuacji. Innymi słowy, jeśli twój los zależy od działań innych, jesteś w grze. Czym jest teoria gier? Teoria gier to studium strategii zaangażowanych w złożone gry. Jest sztuką robienia najlepszego ruchu lub wyboru najlepszej strategii w danej sytuacji w oparciu o cel. Aby to zrobić, należy zrozumieć strategię przeciwnika, a także to, co przeciwnik uważa za twój ruch. Weźmy prosty przykład: jest dwóch rodzeństwa, jeden starszy i drugi młodszy. Teraz w lodówce są dwa lody, jeden to aromat pomarańczowy, a drugi to smak mango. Starszy chce jeść smak pomarańczy, ale wie, czy się na to zdecyduje, a młodszy płakałby za tę samą pomarańczę. Więc wybiera lody o smaku mango i okazuje się zgodne z oczekiwaniami, młodsze chce tego samego. Teraz starszy udaje, że poświęcił lody o smaku mango i podaje je młodszemu i sam je pomarańczowy. Spójrz na sytuację: jest to korzystne dla obu stron, ponieważ był to cel starszego . Jeśli starszy chciał, mógł po prostu walczyć z młodszym dzieckiem i dostać pomarańczową, jeśli to był jego cel. W drugim przypadku starszy starałby się ustalić, gdzie uderzyć, aby młodsze dziecko nie doznało większych obrażeń, ale wystarczająco, by zrezygnował z pomarańczowych lodów. To jest teoria gier: jaki jest twój cel i jaki powinien być twój najlepszy ruch? Jeszcze jeden przykład: tym razem bardziej po stronie biznesu. Wyobraź sobie, że jesteś sprzedawcą dostarczającym warzywa do miasta. Istnieją trzy sposoby, aby dostać się do miasta, z których jedna jest regularną trasą w tym sensie, że wszyscy jeżdżą tą trasą, może dlatego, że jest krótsza i lepsza. Pewnego dnia widzisz, że regularna trasa została zablokowana z powodu pewnych działań naprawczych iw żaden sposób nie możesz przejść tą trasą. Pozostały Ci dwie inne trasy. Jedna z nich to krótka trasa do miasta docelowego, ale jest trochę wąska. Druga jest trochę dłuższa, ale wystarczająco szeroka. Tutaj musisz ustalić strategię, którą trasę dwóch musisz pokonać. Sytuacja może być taka, że ​​na drogach jest duży ruch i wiele osób będzie próbowało pokonać najkrótszą trasę. Może to prowadzić do dużego zatłoczenia na tej trasie i może spowodować ogromne opóźnienie. Zdecydowałeś się więc na dłuższą drogę, aby dotrzeć do miasta na czas, ale kosztem kilku dodatkowych dolarów wydanych na paliwo. Jesteś pewien, że możesz łatwo otrzymać za to wynagrodzenie, jeśli przyjedziesz na czas i sprzedasz warzywa wcześnie po dobrej cenie. To jest teoria gier: jaki jest twój najlepszy ruch dla celu, który masz na myśli, a który zwykle polega na znalezieniu optymalnego rozwiązania.

W wielu sytuacjach zarówno rola, jaką odgrywasz, jak i cel odgrywają istotną rolę w formułowaniu strategii. Przykład: jeśli jesteś organizatorem wydarzenia sportowego, a nie uczestnikiem zawodów, sformułujesz strategię, w której Twoim celem może być, aby uczestnicy grali według zasad i postępowali zgodnie z protokołem. To dlatego, że nie obchodzi cię, kto wygra na końcu, jesteś tylko organizatorem. Z drugiej strony uczestnik planuje zwycięskie ruchy, biorąc pod uwagę mocne i słabe strony przeciwnika oraz zasady narzucone przez organizatora, ponieważ mogą wystąpić kary, jeśli złamiesz zasady. Rozważmy teraz tę sytuację, gdy grasz rolę organizatora. Powinieneś rozważyć, czy może dojść do sytuacji, w której uczestnik łamie regułę i traci jeden punkt, ale rani przeciwnika tak bardzo, że nie może już dłużej konkurować. Musisz więc wziąć pod uwagę to, co uczestnicy mogą myśleć i odpowiednio ustawić swoje zasady. Spróbujmy ponownie zdefiniować teorię gier w oparciu o to, czego dowiedzieliśmy się z poprzednich przykładów. Jest to metoda modelowania rzeczywistych sytuacji w formie gry i analizowania, jaka najlepsza strategia lub ruch osoby lub podmiotu może być w danej sytuacji dla pożądanego rezultatu. Koncepcje z teorii gier są szeroko stosowane w prawie każdym aspekt życia, taki jak polityka, media społecznościowe, planowanie miast, licytowanie, zakłady, marketing, rozproszone przechowywanie, rozproszone przetwarzanie, łańcuchy dostaw i finanse, żeby wymienić tylko kilka. Korzystając z koncepcji teoretycznych gier, możliwe jest zaprojektowanie systemów, w których uczestnicy bawią się zgodnie z zasadami, nie przyjmując ich emocjonalnych i moralnych wartości. Jeśli chcesz wyjść poza budowanie dowodu koncepcji i wprowadzić swój produkt lub rozwiązanie do produkcji, powinieneś traktować teorię gier jako jeden z najważniejszych elementów. Może pomóc zbudować solidne rozwiązania i przetestować je z różnymi interesującymi scenariuszami. Cóż, wielu ludzi już myśli w teorii gier, nie wiedząc, że to teoria gier. Jeśli jednak jesteś wyposażony w wiele narzędzi i technik z teorii gier, to zdecydowanie pomaga.

Kryptografia klucza symetrycznego a asymetrycznego

Przyjrzeliśmy się różnym aspektom i typom algorytmów klucza symetrycznego i asymetrycznego. Oczywiście ich cele projektowe i implikacje są różne. Dokonajmy analizy porównawczej, abyśmy użyli właściwej w odpowiednim miejscu.

  • Kryptografia klucza symetrycznego jest również nazywana kryptografią klucza prywatnego. Podobnie asymetryczna kryptografia klucza jest również nazywana kryptografią klucza publicznego.
  • Wymiana kluczy lub ich dystrybucja w symetrycznej kryptografii klucza jest dużym problemem, w przeciwieństwie do asymetrycznej kryptografii kluczowej.
  • Szyfrowanie asymetryczne jest dość intensywne obliczeniowo, ponieważ długość kluczy jest zwykle duża. W związku z tym proces szyfrowania i deszyfrowania jest wolniejszy. Wręcz przeciwnie, szyfrowanie symetryczne jest szybsze.
  • Kryptografia klucza symetrycznego jest odpowiednia dla długich wiadomości, ponieważ szybkość szyfrowania / deszyfrowania jest szybka. Asymetryczna kryptografia kluczy jest odpowiednia dla krótkich wiadomości, a szybkość szyfrowania / deszyfrowania jest powolna.
  • W symetrycznej kryptografii kluczowej symbole w tekście jawnym i zaszyfrowanym są permutowane lub zastępowane. W asymetrycznej kryptografii kluczowej tekst jawny i tekst zaszyfrowany są traktowane jako liczby całkowite.
  • W wielu sytuacjach, gdy klucz symetryczny jest używany do szyfrowania i deszyfrowania, technika klucza asymetrycznego jest używana do dzielenia się i uzgadniania klucza używanego w szyfrowaniu.
  • Asymetryczna kryptografia klucza znajduje najsilniejsze zastosowanie w niezaufanych środowiskach, gdy zaangażowane strony nie mają wcześniejszego związku. Ponieważ nieznane strony nie mają wcześniejszych możliwości ustanowienia wspólnych kluczy tajnych, udostępnianie poufnych danych jest zabezpieczone za pomocą kryptografii klucza publicznego.
  • Symetryczne techniki kryptograficzne nie umożliwiają podpisów cyfrowych, które są możliwe tylko dzięki kryptografii asymetrycznej.
  • Innym dobrym przykładem jest liczba kluczy wymaganych przez grupę węzłów do komunikacji między sobą. Jak myślisz, ile kluczy byłby potrzebny, na przykład, 100 uczestnikom, gdy potrzebna jest symetryczna kryptografia klucza? Ten problem ze znalezieniem potrzebnych kluczy można traktować jako kompletny problem graficzny z kolejnością 100. Jak każdy wierzchołek wymaga 99 połączonych krawędzi, aby połączyć się ze wszystkimi, każdy uczestnik potrzebuje 99 kluczy, aby ustanowić bezpieczne połączenia ze wszystkimi innymi węzłami. W sumie potrzebne byłyby klucze 100 * (100-1) / 2 = 4.950. Można ją uogólnić dla „n” liczby uczestników w sumie jako n * (n – 1) / 2 kluczy. Wraz ze wzrostem liczby uczestników staje się koszmarem! Jednak w przypadku asymetrycznej kryptografii kluczowej każdy uczestnik potrzebuje tylko dwóch kluczy (jednego prywatnego i jednego publicznego). W przypadku sieci składającej się ze 100 uczestników całkowita liczba potrzebnych kluczy wynosiłaby zaledwie 200.

Wymiana kluczy Diffie-Hellmana

W poprzednich sekcjach przyglądaliśmy się już kryptografii symetrycznej. Przypomnij sobie, że dzielenie się sekretem między nadawcą a odbiorcą jest bardzo dużym wyzwaniem. Z reguły wiemy, że kanał komunikacyjny jest zawsze niepewny. Zawsze może być Ewa próbująca przechwycić twoją wiadomość, gdy jest ona przesyłana za pomocą różnych rodzajów ataków. Technika DH została opracowana do bezpiecznej wymiany kluczy kryptograficznych. Oczywiście trzeba się zastanawiać, jak bezpieczna wymiana kluczy jest możliwa, gdy sam kanał komunikacyjny jest niezabezpieczony. Cóż, w dalszej części tej sekcji zobaczysz, że technika DH nie dzieli tak naprawdę całego tajnego klucza między dwie strony, a raczej tworzy razem klucz. Pod koniec dnia ważne jest, aby nadawca i odbiorca mieli ten sam klucz. Należy jednak pamiętać, że nie jest to asymetryczna kryptografia klucza szyfrowanie / decrytion nie odbywa się podczas wymiany. W rzeczywistości była to podstawa, na której później została zaprojektowana asymetryczna kryptografia klucza. Powodem, dla którego przyglądamy się tej technice teraz, jest to, że wiele matematyki, które już zbadaliśmy w poprzedniej sekcji, jest tutaj przydatne. Najpierw spróbujmy zrozumieć pojęcie na wysokim poziomie, zanim przejdziemy do matematycznego wyjaśnienia. Spójrz na poniższe, gdzie proste wyjaśnienie algorytmu DH jest przedstawione za pomocą kolorów.

Zauważ, że tylko żółty kolor był dzielony między dwie strony w pierwszym kroku, który może reprezentować dowolny inny kolor lub numer randonu. Obie strony dodają do niej swój własny sekret i tworzą mieszankę. Ta mieszanka jest ponownie udostępniana przez ten sam niezabezpieczony kanał. Poszczególne strony dodają do tego swój sekret i tworzą ostateczny wspólny sekret. W tym przykładzie z kolorami zauważ, że wspólne sekrety to połączenie tych samych zestawów kolorów. Spójrzmy teraz na rzeczywiste kroki matematyczne, które mają miejsce przy generowaniu kluczy:

  • Alicja i Bob zgadzają się co do P = 23 i G = 9
  • Alicja wybiera klucz prywatny a = 4, oblicza 94 mod 23 = 6 i wysyła go do Boba
  • Bob wybiera klucz prywatny b = 3, oblicza 93 mod 23 = 16 i wysyła go do Alicji
  • Alicja oblicza 164 mod 23 = 9
  • Bob oblicza 63 mod 23 = 9

Jeśli wykonasz te czynności, znajdziesz zarówno Alice, jak i Boba są w stanie wygenerować ten sam tajny klucz na ich końcach, który może być użyty do szyfrowania / deszyfrowania. Użyliśmy małych liczb w tym przykładzie dla łatwego zrozumienia, ale duże liczby pierwsze są używane w rzeczywistych przypadkach użycia. Aby lepiej to zrozumieć, przejrzyjmy następujący fragment kodu i zobaczmy, w jaki sposób algorytm DH można zaimplementować w prosty sposób:

/ * Program do obliczania kluczy dla dwóch stron za pomocą algorytmu wymiany klucza Diffie-Hellmana * /

// funkcja zwracająca wartość a ^ b mod P

long long int power(long long int a, long long int b, long long

int P)

{

if (b == 1)

return a;

else

return (((long long int)pow(a, b)) % P);

}

// Główny program do obliczania klucza DH

int main()

{

long long int P, G, x, a, y, b, ka, kb;

// Obie strony uzgadniają klucze publiczne G i P

P = 23; // Przyjmuje się liczbę pierwszą P

printf (“Wartość P:% lld n”, P);

G = 9; // Pierwotny root dla P, G jest pobierany

printf (“Wartość G:% lld n”, G);

// Alice wybierze klucz prywatny a

a = 4; // a jest wybranym kluczem prywatnym

printf (“Klucz prywatny a dla Alice:% lld n”, a);

x = power(G, a, P); // pobiera wygenerowany klucz

// Bob wybierze klucz prywatny b

b = 3; //b jest wybranym kluczem prywatnym

printf(“Prywatny klucz b dla Boba : %lld\n\n”, b);

y = power(G, b, P); // pobiera wygenerowany klucz

// Generowanie tajnego klucza po wymianie kluczy

ka = power(y, a, P); // Tajny klucz dla Alice

kb = power(x, b, P); // Tajny klucz Boba

printf(“Tajny klucz dla Alice to : %lld\n”, ka);

printf(“Tajny klucz dla Boba to : %lld\n”, kb);

return 0;

}

Uwaga W przypadku tradycyjnego problemu z logarytmem dyskretnym (xy  mod  p), ogólny proces można zmodyfikować również w celu wykorzystania kryptografii krzywej eliptycznej.

Przykładowy kod kryptografii klucza asymetrycznego

Poniżej znajdują się przykłady kodu różnych algorytmów publicznych. Ta sekcja ma na celu zapoznanie Cię z programowaniem różnych algorytmów. Przykłady kodu znajdują się w Pythonie, ale byłyby podobne w różnych językach; po prostu musisz znaleźć odpowiednie funkcje biblioteki, których chcesz użyć

# -*- coding: utf-8 -*-

import Crypto

from Crypto.PublicKey import RSA

from Crypto import Random

from hashlib import sha256

#Funkcja generowania kluczy o domyślnej długości 1024

def generate_key(KEY_LENGTH=1024):

random_value= Random.new().read

keyPair=RSA.generate(KEY_LENGTH,random_value)

return keyPair

# Generuj klucz do ALICE i BOB

bobKey=generate_key()

aliceKey=generate_key()

# Wydrukuj klucz publiczny Alice i Boba. Ten klucz może być udostępniony

alicePK=aliceKey.publickey()

bobPK=bobKey.publickey()

print “Alice’s Public Key:”, alicePK

print “Bob’s Public Key:”, bobPK

# Alice chce wysłać tajną wiadomość do Boba. Pozwala stworzyć

fikcyjną wiadomość dla Alicji

secret_message=”Alice’s secret message to Bob”

print “Message”, secret_message

secret_message=”Alice’s secret message to Bob”

print “Message”, secret_message

# Funkcja generowania podpisu

def generate_signature(key,message):

message_hash=sha256(message).digest()

signature=key.sign(message_hash,”)

return signature

# Pozwala wygenerować podpis tajnej wiadomości

alice_sign=generate_signature(aliceKey,secret_message)

#  Przed wysłaniem wiadomości w sieci zaszyfruj wiadomość za pomocą

klucza publicznego Boba ..

encrypted_for_bob = bobPK.encrypt(secret_message, 32)

# Bob odszyfrowuje tajną wiadomość za pomocą własnego klucza prywatnego …

decrypted_message = bobKey.decrypt(encrypted_for_bob)

print “Decrypted message:”, decrypted_message

# Bob użyje następującej funkcji, aby zweryfikować podpis

od Alice używając jej klucza publicznego

def verify_signature(message,PublicKey,signature):

message_hash=sha256(message).digest()

verify = PublicKey.verify(message_hash,signature)

return verify

# bob sprawdza za pomocą odszyfrowanej wiadomości i publicznego klucza alice

print “Is alice’s signature for decrypted message valid?”,

verify_signature(decrypted_message,alicePK, alice_sign)

The ECDSA Algorithm

import ecdsa

# SECP256k1 to krzywa eliptyczna Bitcoin

signingKey = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)

# Uzyskaj klucz weryfikacyjny

verifyingKey = signingKey.get_verifying_key()

# Generuj podpis wiadomości

signature = signingKey.sign(b”signed message”)

# Sprawdź, czy podpis jest ważny lub nieprawidłowy dla wiadomości

verifyingKey.verify(signature, b”signed message”) # True.

Signature is valid

# Sprawdź, czy podpis jest ważny lub nieprawidłowy dla wiadomości

assert verifyingKey.verify(signature, b”message”) # Throws an

error. Signature is invalid for message

Weryfikacja podpisu

Powiedzmy, że Bob jest tutaj odbiorcą i ma dostęp do parametrów domeny i klucza publicznego Q nadawcy Alice. Jako środek bezpieczeństwa Bob powinien najpierw sprawdzić, czy posiadane przez niego dane, czyli parametry domeny, podpis i klucz publiczny Q Alicji są poprawne. Aby zweryfikować podpis Alicji w wiadomości (m), Bob wykona następujące operacje w określonej kolejności:

  • Sprawdź, czy r i s są liczbami całkowitymi w przedziale [1, n – 1]
  • Oblicz e = SHA-1 (m)
  • Oblicz w = s−1 mod n
  • Oblicz u1 = e w mod n, a u2 = r w mod n
  • Oblicz X = u1 G + u2 G, gdzie X oznacza współrzędne, powiedzmy (x2, y2)
  • Oblicz v = x1 mod n
  • Zaakceptuj podpis, jeśli r = v, w przeciwnym razie go odrzuć

W tej sekcji przyjrzeliśmy się matematyce ECDSA. Przypomnij sobie, że podczas generowania klucza i podpisu użyliśmy liczby losowej. Niezwykle ważne jest zapewnienie, że generowane liczby losowe są faktycznie kryptograficznie losowe. W wielu przypadkach używa się 160-bitowego ECDSA, ponieważ musi on pasować do funkcji skrótu SHA-1. Z tak wielu przypadków użycia ECDSA jest wykorzystywana w certyfikatach cyfrowych. W najprostszej formie certyfikat cyfrowy jest kluczem publicznym, dołączonym do identyfikatora urządzenia i daty ważności certyfikatu. W ten sposób certyfikaty umożliwiają nam sprawdzenie i potwierdzenie, do kogo należy klucz publiczny, a urządzenie jest legalnym członkiem rozważanej sieci. Certyfikaty te są bardzo ważne, aby zapobiec „atakowi personifikacji” w protokołach ustanawiania kluczy. Wiele certyfikatów TLS jest opartych na parze kluczy ECDSA i takie wykorzystanie stale rośnie.

Generowanie podpisu

Po wygenerowaniu kluczy Alice, nadawca, użyje klucza prywatnego „d” do podpisania wiadomości (m). Wykonałaby zatem następujące kroki w podanej kolejności, aby wygenerować podpis:

  • Wybierz losową liczbę k w przedziale [1, n – 1]
  • Oblicz k.G i znajdź nowe współrzędne (x1, y1) i

znajdź r = x1 mod n

Jeśli r = 0, zacznij od nowa

  • Oblicz e = SHA-1 (m)
  • Oblicz s = k -1 (e + d. R) mod n

Jeśli s = 0, zacznij od nowa od pierwszego kroku

  • Podpis Alice dla wiadomości (m) będzie teraz (r, s)

Generowanie klucza

Ponieważ parametry domeny (P, a, b, G, n, h) są wstępnie ustalone, krzywa i punkt bazowy są znane obu stronom. Znana jest również liczba pierwsza P, która sprawia, że jest to pole skończone (P ma zwykle 160 bitów i może być również większe). Tak więc, nadawca, powiedzmy, Alice wykonuje następujące czynności, aby wygenerować klucze:

  • Wybierz losową liczbę całkowitą d w przedziale [1, n – 1]
  • Oblicz Q = d G
  • Zadeklaruj Q jest kluczem publicznym i zachowaj d jako klucz prywatny.

Algorytm podpisu cyfrowego eliptycznej krzywej

ECDSA to rodzaj DSA, który wykorzystuje ECC do generowania kluczy. Jak sama nazwa wskazuje, jego celem jest podpis cyfrowy, a nie szyfrowanie. ECDSA może być lepszą alternatywą dla RSA pod względem mniejszego rozmiaru klucza, lepszego bezpieczeństwa i wyższej wydajności. Jest to jeden z najważniejszych elementów kryptograficznych używanych w Bitcoinach! Przyjrzeliśmy się już, jak podpisy cyfrowe są używane do ustanawiania zaufania między nadawcą a odbiorcą. Ponieważ autentyczność nadawcy i integralność wiadomości można zweryfikować za pomocą podpisów cyfrowych, dwie nieznane strony mogą zawierać transakcje między sobą. Należy pamiętać, że nadawca i odbiorca muszą uzgodnić parametry domeny przed rozpoczęciem komunikacji. ECDSA ma trzy kroki: generowanie klucza, generowanie podpisu i weryfikacja podpisu.

Kryptografia eliptycznej krzywej

Kryptografia krzywej eliptycznej (ECC) faktycznie ewoluowała z kryptografii Diffie-Hellmana. Został odkryty jako alternatywny mechanizm do implementacji kryptografii klucza publicznego. W rzeczywistości odnosi się do pakietu protokołu kryptograficznego i opiera się na problemie logarytmu dyskretnego, jak w DSA. Uważa się jednak, że dyskretny problem logarytmiczny jest jeszcze trudniejszy, gdy stosuje się go do punktów na krzywej eliptycznej. Tak więc ECC zapewnia większe bezpieczeństwo dla danego rozmiaru klucza. 160-bitowy klucz ECC jest uważany za tak zabezpieczony jak 1024-bitowy klucz RSA. Ponieważ mniejsze rozmiary kluczy w ECC mogą zapewnić większe bezpieczeństwo i wydajność w porównaniu z innymi algorytmami klucza publicznego, jest on powszechnie stosowany w małych wbudowanych urządzeniach, czujnikach i innych urządzeniach IoT itp. Dostępne są bardzo wydajne implementacje sprzętowe dla ECC. ECC opiera się na matematycznie powiązanym zestawie liczb na krzywej eliptycznej nad polami skończonymi. Nie ma też nic wspólnego z elipsami! Matematycznie krzywa eliptyczna spełnia następujące warunki matematycznego równania:

y2 = x3 + ax + b, gdzie 4a3 + 27b2 ≠ 0

Przy różnych wartościach „a” i „b” krzywa przyjmuje różne kształty, jak pokazano na poniższym schemacie:

Istnieje kilka ważnych cech charakterystycznych krzywych eliptycznych używane w kryptografii, takie jak:

  • Są poziomo symetryczne. tj. to, co znajduje się poniżej osi X, jest lustrzanym odbiciem tego, co znajduje się powyżej osi X. Tak więc każdy punkt na krzywej po odbiciu od osi X nadal pozostaje na krzywej.
  • Każda niewerbalna linia może przecinać krzywą w co najwyżej trzech miejscach.
  • Jeśli rozważysz dwa punkty P i Q na krzywej eliptycznej i narysujesz przez nie linię, linia może dokładnie przeciąć krzywą w jednym miejscu. Nazwijmy to (- R). Jeśli narysujesz pionową linię przechodzącą przez (-R), przekroczy ona krzywą, powiedzmy, R, co jest odbiciem punktu (-R). Trzecia właściwość oznacza, że P + Q = R. Nazywa się to „dodawaniem punktu”, co oznacza, że dodanie dwóch punktów na krzywej eliptycznej doprowadzi cię do innego punktu na krzywej. Zapoznaj się z poniższym diagramem, aby zobaczyć obraz tych trzech właściwości.

Możesz więc dodać punkt do dowolnych dwóch punktów na krzywej. Teraz, w poprzednim punkcie, dodaliśmy P i Q (P + Q) i znaleźliśmy – R, a następnie ostatecznie dotarliśmy do R. Po dotarciu do R, my

może następnie narysować linię od P do R i zobaczyć, że linia przecina wykres ponownie w trzecim punkcie. Możemy wtedy wziąć ten punkt i przesunąć się wzdłuż linii pionowej, aż ponownie przecieje wykres. Staje się to dodatkiem punktowym dla punktów P i R. Proces ten ze stałym P i punktem wynikowym może trwać tak długo, jak chcemy, a my będziemy zdobywać nowe punkty na krzywej.

  • Teraz zamiast dwóch punktów P i Q, jeśli zastosujemy operację do tego samego punktu P, tj. P i P (zwanego „podwojeniem punktu”). Oczywiście, nieskończona liczba linii jest możliwa poprzez P, więc rozważymy tylko linię styczną. Linia styczna przekroczy krzywą jeszcze jeden punkt i pionowa linia ponownie przekroczą krzywą, aby uzyskać końcową wartość. Można to pokazać w następujący sposób:

  • Jest oczywiste, że możemy zastosować punktowe podwojenie liczby punktów „n” do początkowego punktu i za każdym razem doprowadzi nas to do innego punktu na krzywej. Gdy po raz pierwszy zastosowaliśmy podwojenie punktu do punktu P, zabrało nas to do otrzymanego punktu 2P, jak widać na diagramie. Teraz, jeśli to samo powtarza się „n” wiele razy, osiągniemy punkt na krzywej, jak pokazano na poniższym diagramie:

  • W powyższym scenariuszu, gdy podano punkt początkowy i końcowy, nie można powiedzieć, że podwojenie punktu zostało zastosowane „n” razy, aby osiągnąć końcowy wynik, z wyjątkiem próby dla wszystkich możliwych „n” przez jeden. Jest to problem logarytmu dyskretnego dla ECC, gdzie stwierdza się, że dany punkt G i Q, gdzie Q jest wielokrotnością G, znajduje „d” w taki sposób, że Q = d G. To tworzy funkcję jednokierunkową bez skrótów. Tutaj Q jest kluczem publicznym, a d jest kluczem prywatnym. Czy możesz wyodrębnić klucz prywatny d z klucza publicznego Q? Jest to problem logarytmu dyskretnego krzywej eliptycznej, który jest trudny do obliczenia.
  • Co więcej, krzywa powinna być zdefiniowana nad skończonym polem, a nie prowadzić do nieskończoności! Oznacza to, że wartość „max” na osi X musi być ograniczona do pewnej wartości, więc po prostu rzuć wartości po osiągnięciu maksimum. Ta wartość jest reprezentowana jako P (nie jest to P stosowane na wykresach tutaj) w kryptosystemie ECC i jest nazywana wartością „modulo”, a także definiuje rozmiar klucza, stąd pole skończone. dla „P” jest wybrane.
  • Zwiększony rozmiar „P” skutkuje bardziej użytecznymi wartościami na krzywej, a tym samym większym bezpieczeństwem.
  • Zaobserwowaliśmy, że dodawanie punktów i podwajanie punktów stanowią podstawę do znalezienia wartości używanych do szyfrowania i deszyfrowania.

Aby zdefiniować ECC, należy zdefiniować następujące parametry domeny:

  • Równanie krzywej: y2 = x3 + ax + b, gdzie 4a3 + 27b2 ≠ 0
  • P: liczba pierwsza, która określa pole skończone, przez które krzywa zostanie zdefiniowana (wartość modulo)
  • a i b: współczynniki definiujące krzywą eliptyczną
  • G: punkt bazowy lub punkt generatora na krzywej. Jest to punkt, w którym rozpoczynają się wszystkie operacje punktowe i definiuje podgrupę cykliczną.
  • n: liczba operacji punktowych na krzywej, aż wynikowa linia będzie pionowa. Zatem jest to kolejność G, tj. Najmniejsza dodatnia liczba taka, że ​​nG = ∞. Zwykle jest prime.
  • h: Nazywa się „kofaktorem”, który jest równy kolejności krzywej podzielonej przez n. Jest to wartość całkowita i zwykle bliska 1.

Zauważ, że ECC to świetna technika do generowania kluczy, ale jest używana obok innych technik podpisów cyfrowych i wymiany kluczy. Na przykład, Elliptic Curve Diffie-Hellman (ECDH) jest dość popularnie używany do wymiany kluczy, a ECDSA jest używany do podpisów cyfrowych.

Algorytm podpisu cyfrowego

DSA został zaprojektowany przez NSA jako część standardu Digital Signature Standard (DSS) i standaryzowany przez NIST. Zauważ, że jego głównym celem jest podpisywanie wiadomości cyfrowo, a nie szyfrowanie. Parafrazując, RSA służy zarówno do zarządzania kluczami, jak i do uwierzytelniania, podczas gdy DSA służy tylko do uwierzytelniania. Ponadto, w przeciwieństwie do RSA, który opiera się na rozkładzie dużych liczb, DSA opiera się na dyskretnych logarytmach. Na wysokim poziomie używany jest DSA, jak pokazano na rysunku

Jak widać na rysunku, wiadomość jest najpierw mieszana, a następnie podpisywana, ponieważ jest bardziej zabezpieczona w porównaniu z podpisywaniem, a następnie mieszaniem. Najlepiej byłoby zweryfikować autentyczność przed wykonaniem jakiejkolwiek innej operacji. Tak więc po podpisaniu wiadomości podpisany skrót jest oznaczany wiadomością i wysyłany do odbiorcy. Odbiorca może następnie sprawdzić autentyczność i znaleźć skrót. Ponadto zmień komunikat, aby ponownie uzyskać skrót i sprawdź, czy oba skróty są zgodne. W ten sposób DSA zapewnia następujące właściwości zabezpieczeń:

  • Autentyczność: Podpisany kluczem prywatnym i zweryfikowany kluczem publicznym
  • Integralność danych: skróty nie będą zgodne, jeśli dane zostaną zmienione.
  • Niezaprzeczalność: ponieważ nadawca go podpisał, nie może później odmówić wysłania wiadomości. Niezaprzeczalność to właściwość, która jest najbardziej pożądana w sytuacjach, w których istnieje szansa na spór o wymianę danych. Na przykład po złożeniu zamówienia elektronicznie nabywca nie może odmówić zamówienia, jeśli w takiej sytuacji możliwe jest niezaprzeczenie. Typowy schemat DSA składa się z trzech algorytmów: (1) generowanie klucza, (3) generowanie podpisu i (3) weryfikacja podpisu