Matematyka.pl

Po pierwsze te bloki miały mieć nie \(\displaystyle{ p}\), lecz tyle cyfr, ile ma \(\displaystyle{ p}\). Potem powieliłem ten błąd.

Po drugie element pierwotny istnieje dla każdej liczby pierwszej \(\displaystyle{ p}\) i dość często jest to mała liczba pierwsza. Liczby pierwsze i elementy pierwotne są do znalezienia w różnych tabelach.

Po trzecie żeby każdemu szyfrowi tego typu odpowiadała dokładnie jedna trójka \(\displaystyle{ A,B,C}\), liczba pierwsza \(\displaystyle{ p}\) musi być większa od \(\displaystyle{ 1000}\).

Przykład. Liczba pierwsza to niech na przykład: \(\displaystyle{ p=43}\). Dwucyfrowa, więc będziemy dzielić na bloki dwucyfrowe. Jeśli liczba cyfr danej liczby nie jest parzysta, to dopisujemy na początku jedno zero. I ogólnie; jeśli dzielimy na bloki \(\displaystyle{ n}\)-cyfrowe, to w razie potrzeby dopisujemy \(\displaystyle{ 1,2...,n-1}\) zer na początku. Liczba \(\displaystyle{ 43}\) to zdaje się najmniejsza liczba pierwsza dla której \(\displaystyle{ 2}\) nie jest elementem pierwotnym: \(\displaystyle{ 2^{14}-1}\) dzieli się przez \(\displaystyle{ 43}\). Za to \(\displaystyle{ q=3}\) jest elementem pierwotnym. Zamiast \(\displaystyle{ A,B,C}\) bierzemy liczby 3-cyfrowe. Na przykład trójce \(\displaystyle{ 0,2,7}\) odpowiada liczba \(\displaystyle{ k=27}\). Dla \(\displaystyle{ p=43}\), czyli małej liczby pierwszej możemy jednoznacznie kodować liczby niewiększe niż \(\displaystyle{ 42}\). W praktyce używa się kilkudziesięciocyfrowych liczb pierwszych i nie ma takiego problemu.

Kila początkowych wartości funkcji \(\displaystyle{ f(x)=3^{x+27}\mod 43}\)

\(\displaystyle{ f(0)=0}\), co zapiszemy:

\(\displaystyle{ \sf{00}\mapsto \sf{00}}\)

podobnie \(\displaystyle{ f(1)=1}\):

\(\displaystyle{ \sf{01}\mapsto \sf{01}}\)

\(\displaystyle{ f(\textcolor{blue}2)=18}\), bo \(\displaystyle{ 3^{\textcolor{blue}2+27}=18\mod 43}\).

czyli:

\(\displaystyle{ \sf{02}\mapsto \sf{18}}\)

Dalej:

\(\displaystyle{ \sf{03}\mapsto \sf{11}}\)

\(\displaystyle{ \sf{04}\mapsto \sf{33}}\)

\(\displaystyle{ \sf{05}\mapsto \sf{13}}\)

\(\displaystyle{ \sf{06}\mapsto \sf{39}}\)

\(\displaystyle{ \sf{07}\mapsto \sf{30}}\)

\(\displaystyle{ \sf{08}\mapsto \sf{08}}\)

\(\displaystyle{ \sf{09}\mapsto \sf{21}}\)

\(\displaystyle{ \sf{10}\mapsto \sf{20}}\)

Przykładowo dla liczby trzycyfrowej \(\displaystyle{ 341}\):

\(\displaystyle{ \sf{0341}\mapsto \sf{1115}}\).

Złamanie szyfru jest stosunkowo łatwe dla małych liczb pierwszych \(\displaystyle{ p}\), wystarczy rozważyć wszystkie \(\displaystyle{ p-2}\) możliwości. Dla kilkudziesięciocyfrowych liczb pierwszych rozważanie wszystkich możliwości jest niepraktyczne i pewnie technicznie niewykonalne, przynajmniej póki co.

Wielkie dzięki!
Wiedziałem, że algorytmy temu służące są oparte o liczby pierwsze, tylko nie wiedziałem jak.

Jeszcze dopytam:
Ile par X Y potrzeba, żeby znać następny Y dla danego X w oparciu o ten algorytm? nieskończenie wiele?
Nie mogę znaleźć tych tabel liczb pierwszych i elementów pierwotnych. Ktoś wspomoże linkiem?

No i jak rozumiem odpowiedzią na cały założony przezemnie temat jest RSA (algorytm kryptografi).

Wszystkim dziękuje.

Już jedna para \(\displaystyle{ x, y=q^{x+k}\mod p}\) wystarcza do wyznaczenia \(\displaystyle{ k}\), ale póki co nie w czasie wielomianowym względem liczby cyfr \(\displaystyle{ p}\).

Jeśli chcemy nieco lepiej zamaskować A,B,C możemy rozważyć:

\(\displaystyle{ x\mapsto q(A,B,C)^x\mod p}\)

gdzie \(\displaystyle{ q(A,B,C)}\)to najmniejszy element pierwotny modulo \(\displaystyle{ p}\) niemniejszy niż \(\displaystyle{ 100A+10B+C}\). Wyznaczenie tego elementu nie jest trudne. Elementy niepierwotne są raczej rzadkie, więc wystarczy po kolei sprawdzić kilka możliwości, na ogół \(\displaystyle{ 100A+10B+C}\) zadziała. Jak poprzednio wspominałem to daje \(\displaystyle{ jedynie}\) co najwyżej 1000 razy dłuższy czas łamania szyfru.

Może inaczej sformułuje pytanie:
Jedna rzecz to to, żeby nie dało się zdekodować ABC, bo potem wystarczy podstawić dane pod wzór żeby mieć Y dla nowego X.
A druga to to, aby nie dało się przewidzieć jakie będzie Y dla danego X, znając kilkanaście par X Y.
Chodzi o to, czy da się i po uzyskaniu ilu par X Y w "sensownym czasie" przewidzieć Y dla X, które nie pojawiło się wśród tych par?

Niezależne od pierwszego pytanie 2:
I jeszcze chciał bym napisać jak ja to rozumiem, i dowiedzieć się gdzie robię błąd? Jeżeli w pierwszym wzorze:
\(\displaystyle{ Y=Q^{X+A} mod p}\)
p - liczba pierwsza
A - hasło
Q - element pierwotny zależny od p
X - zmienna
To zakładając że p jest również tajne, to łatwo(?) je uzyskać wiedząc że p jest niewiele większe, bądź równe max Y (ze znanych kilkunastu par X Y). A jak zgadniemy p to znamy również Q(rozumiem że dane p ma tylko jedno Q) i robi się równanie z jedną niewiadomą. Czy gdzieś robię błąd?
Nie widzę sensu żeby ujawniać użyte liczby pierwsze P i Q. (Ale to już kosmetyka)

pytanie 3:
Czemu gdy Q i P będą dowolnymi liczbami całkowitymi tajnymi wybranymi w ramach hasła będzie łatwiej złamać hasło?

Przepraszam, że odświeżam, ale zastanawia mnie czy mój wzór nie spełnia przypadkiem warunków. Nie mam dowodu co do tego, że nie znając ABC i znając wiele par (X,Y) nie da się wyliczyć następnej, ale mam podejrzenie

\(\displaystyle{ Y= \lfloor \frac{X}{A} \rfloor + \lceil \frac{XB}{3} + \frac{ C^{X} }{5} \rceil}\)

Przykładowe wartości:
\(\displaystyle{ \begin{array}{cc}X&Y\\0&1\\1&1\\2&3\\3&2\\4&7\\11&-399\\60&230584300921369456\end{array}}\)