Zagadka o KLUCZU

[myslewiecjestem]

trapiaca kryptologow od czasow zamierzchlych bylo rozwiazanie problemu
nastepujacego: jak przeslac nie tylko potajemna wiadomosc do odbiorcy,
ale i KLUCZ prowadzacy do rozwiazania. Ci, ktorzy byli zainteresowani
przechwytywaniem czyjejs korespondencji, z rowna sila starali sie dowiedziec
o sposobie rozwiazania zagadki. Dla przykladu: wysylem do swojego wujka
zaszyfrowany tekst. Robimy to od lat i wiemy jaki klucz wujek musi uzyc by
odczytac wiadomosc. Teraz, chce wyslac wiadomosc do kogos, kogo poznalem
przypadkowo i nie mialem mozliwosci rozmawiac o kluczu do rowzwiazywania
szyfru, nie wspominajac o tym, ze nie planowalem zadnej korespondencji,
w tym zaszyfrowanej, do nowego znajomego. Ten sam problem powstanie z moim
wujkiem, jesli podejmiemy sie zmiany KLUCZA.
Oto wiec zagadka, ktorej rozwiazanie dalo prapoczatek do wspolczesnej
kryptografii i tzw. asymetrycznego, podwojnego klucza.

Pani X wysyla w metalowej skrzynce wiadomosc. Skrzynka ta jest
zabezpieczona metalowa klodka, do ktorej klucz jest w posiadaniu Pani X.
Klucz nie zostaje wyslany do odbiorcy, Pani Y. Pytanie: co musi Pani Y zrobic
by otworzyc skrzynke i w konsekwencji miec dostep do tajemnej korespondencji ?
Powtarzam, Pani Y dostala tylko skrzynke z zalozona klodka ale nie ma klucza
do tej klodki.
Zawolanie slusarza nie wchodzi w rachube i oczywiscie jakiekolwiek rozbijanie
skrzynki.
Dobrej zabawy.
Zapraszam na forum Klub "Szyfrogram".
Pozdr, Myslewiecjestem.

[Gość: Baton]

Nie chce mi sie pisac rozwiazania bo moze
ktos jeszcze tego nie zna, ale czy przypadkiem
tego typu zagadka juz sie raz tutaj nie pojawila
w kontekscie filatelisty (czy jakiegos innego
zbieracza) chcacego anonimowo odsprzedac
komus innemu czesc swojej kolekcji???

[myslewiecjestem]

Gość portalu: Baton napisał(a):

> Nie chce mi sie pisac rozwiazania bo moze
> ktos jeszcze tego nie zna, ale czy przypadkiem
> tego typu zagadka juz sie raz tutaj nie pojawila
> w kontekscie filatelisty (czy jakiegos innego
> zbieracza) chcacego anonimowo odsprzedac
> komus innemu czesc swojej kolekcji???

Mozliwe. Tylko czy wtedy potrzebny bylby ten caly zamet ? Rozwiazanie jest
swego rodzaju klopotem i o anonimowosci nie moze byc mowy. Pamietaj ze
wymieniajac takie skarby jakie zawiera metalowa szkatula, lepiej zeby
bylo wiadomo, kto z kim i po co .
Pozdr, Myslewiecjestem.

[kopperek]

Nie rozwiązywałem tamtej zagadki, o której pisze Baton.
Więc mam prawo do watpliwości.

Przede wszystkim - rozumiem, że rzecz w tym, aby ta
uprawniona osoba była w stanie odczytać wiadomość, a ktoś
postronny, kto prypadkiem wszedłby w jej posiadanie - już
nie. Czyli musi istnieć jakaś dodatkowa wymiana
infromacji pomiędzy X i Y, i w dodatku zakładamy, że ta
już w ręce draba, powiedzmy Z, nie wpadnie. Poprzez
wymianę informacji rozumiem także wcześniejszą ustną
umowę czy cokolwiek w tym guście. Czy ja w ogóle rozumuję
w dobrym kierunku?

Kopperek

[myslewiecjestem]

kopperek napisał:

> Nie rozwiązywałem tamtej zagadki, o której pisze Baton.
> Więc mam prawo do watpliwości.
>
> Przede wszystkim - rozumiem, że rzecz w tym, aby ta
> uprawniona osoba była w stanie odczytać wiadomość, a ktoś
> postronny, kto prypadkiem wszedłby w jej posiadanie - już
> nie. Czyli musi istnieć jakaś dodatkowa wymiana
> infromacji pomiędzy X i Y, i w dodatku zakładamy, że ta
> już w ręce draba, powiedzmy Z, nie wpadnie. Poprzez
> wymianę informacji rozumiem także wcześniejszą ustną
> umowę czy cokolwiek w tym guście. Czy ja w ogóle rozumuję
> w dobrym kierunku?
>
> Kopperek

Rozumujesz. Caly problem polega na tym, by umozliwic Pani A przeslac wiadomosc
do Pani B BEZ UPRZEDNIEGO DOGADANIA SIE CO DO KLUCZA. Ten problem nazywa sie
fachowo Key-Distribution. Chodzi wlasnie o to by nie musialo byc dodatkowej
wymiany informacji, gdyz to wlasnie powoduje problemy.
Pozdr, Myslewiecjestem.

[kopperek]

myslewiecjestem napisał:

> Caly problem polega na tym, by umozliwic Pani A
przeslac wiadomosc
> do Pani B BEZ UPRZEDNIEGO DOGADANIA SIE CO DO KLUCZA.
Ten problem nazywa sie
> fachowo Key-Distribution. Chodzi wlasnie o to by nie
musialo byc dodatkowej
> wymiany informacji, gdyz to wlasnie powoduje problemy.
> Pozdr, Myslewiecjestem.

No ale - jeśli nie ma tej wymiany, to pani Y (wg
pierwotnej terminologii) jest w dokładnie tej samej
sytuacji, co drab Z, który wszedł w posiadanie informacji
przypadkiem. Czegoś nie kumam.

Kopperek

[myslewiecjestem]

kopperek napisał:

> myslewiecjestem napisał:
>
> > Caly problem polega na tym, by umozliwic Pani A
> przeslac wiadomosc
> > do Pani B BEZ UPRZEDNIEGO DOGADANIA SIE CO DO KLUCZA.
> Ten problem nazywa sie
> > fachowo Key-Distribution. Chodzi wlasnie o to by nie
> musialo byc dodatkowej
> > wymiany informacji, gdyz to wlasnie powoduje problemy.
> > Pozdr, Myslewiecjestem.
>
> No ale - jeśli nie ma tej wymiany, to pani Y (wg
> pierwotnej terminologii) jest w dokładnie tej samej
> sytuacji, co drab Z, który wszedł w posiadanie informacji
> przypadkiem. Czegoś nie kumam.
>
> Kopperek

W tym problemie sa dwa klucze. Jeden u pani wysylajacej i drugi i pani
odbierajacej. Tylko jak to zrobic, by kazda z tych pan miala zawsze przy sobie
swoj klucz, i nie byloby mozliwosci przechwycenia zadnego z tych kluczy ?
Rozwiazanie tej zagadki doprowadzilo do powstania tzw Public i Private Keys,
czyli systemow, ktore uzywamy dzisiaj i ktore sa w praktyce nie do pokonania.
Pomysl jeszcze troche. Potem juz chyba podam Ci rozwiazanie.
Pozdr, Myslewiecjestem.

[speedyartur]

Podaj więc...

[kopperek]

ok, usuwam się w cień i proszę o rozwiązanie.

Kopperek

[myslewiecjestem]

kopperek napisał:

> ok, usuwam się w cień i proszę o rozwiązanie.
>
> Kopperek

OK. Pani A wysyla zelazna skrzynke ze swoja klodka. Klucze trzyma u siebie,
nie wysylajac ich. Pani B otrzymuje przesylke, zaklada swoja klodke i wysyla
do Pani A przesylke, bez wysylania klucza. Pani A po otrzymaniu przesylki
odpina swoja klodke (do ktorej przeciez ma klucz)i wysyla spowrotem skrzynke
do Pani B. Panie B otwiera swoja klodke kluczem, z ktorym ani na chwile sie nie
rozstala.
Wierzcie albo i nie. Ten pomysl stworzyl podwaliny pod dzisiajszy system kluczy,
prywatnych i publicznych.
Pozdr, Myslewiecjestem.

[kopperek]

myslewiecjestem napisał:

> OK. Pani A wysyla zelazna skrzynke ze swoja klodka.
Klucze trzyma u siebie,
> nie wysylajac ich. Pani B otrzymuje przesylke, zaklada
swoja klodke i wysyla
> do Pani A przesylke, bez wysylania klucza. Pani A po
otrzymaniu przesylki
> odpina swoja klodke (do ktorej przeciez ma klucz)i
wysyla spowrotem skrzynke
> do Pani B. Panie B otwiera swoja klodke kluczem, z
ktorym ani na chwile sie nie
>
> rozstala.
> Wierzcie albo i nie. Ten pomysl stworzyl podwaliny pod
dzisiajszy system kluczy
> ,
> prywatnych i publicznych.
> Pozdr, Myslewiecjestem.

Skąd A wie, kiedy dostanie zwrotnie przesyłkę, że ta
druga kłódka pochodzi właśnie od B? Bo jeśli przechwycił
ją i odesłał (z własną kłódką) ten drab, to A nie powinna
swojej kłódki zdejmować.

Kopperek

[myslewiecjestem]

kopperek napisał:

> myslewiecjestem napisał:
>
> > OK. Pani A wysyla zelazna skrzynke ze swoja klodka.
> Klucze trzyma u siebie,
> > nie wysylajac ich. Pani B otrzymuje przesylke, zaklada
> swoja klodke i wysyla
> > do Pani A przesylke, bez wysylania klucza. Pani A po
> otrzymaniu przesylki
> > odpina swoja klodke (do ktorej przeciez ma klucz)i
> wysyla spowrotem skrzynke
> > do Pani B. Panie B otwiera swoja klodke kluczem, z
> ktorym ani na chwile sie nie
> >
> > rozstala.
> > Wierzcie albo i nie. Ten pomysl stworzyl podwaliny pod
> dzisiajszy system kluczy
> > ,
> > prywatnych i publicznych.
> > Pozdr, Myslewiecjestem.
>
> Skąd A wie, kiedy dostanie zwrotnie przesyłkę, że ta
> druga kłódka pochodzi właśnie od B? Bo jeśli przechwycił
> ją i odesłał (z własną kłódką) ten drab, to A nie powinna
> swojej kłódki zdejmować.
>
> Kopperek

Masz racje kopperku. To jest jednak tylko model, szkic do czegos o wiele
bardziej skomplikowanego. W realu, nawet jak ktos by przechwycil wiadomosc,
to nie bylby w stanie zalozyc swojej klodki i zmylic Pania A. W realu wiadomosc
nie krazy tam i z powrotem tylko raz wyslana trafia do Pani B i Pani B otwiera
swoim kluczem. Wyglada to tak ze Pani B podaje do wiadomosci publicznej swoj
Klucz A wedlug ktorego kazdy moze napisac do niej co chce, szyfrujac to, ale
tylko ona moze odczytac ta przesylke posiadajac druga czesc klucza, KLucz B.
Nie miejsce tu na matematyke i sposob w jaki to zrobiono ale jest to niezwykle
pewny system i zeby go zlamac, potrzebaby.... pracy milionow komputerow razy
czas trwania wszechswiata. Chyba ze znajdzie sei jakis geniusz klasy Einsteina
i pokaze prosty wzor na zlamanie tej metody.
Pozdr, Myslewiecjestem.

[kopperek]

Aaaa, tak to ok!

Czyli - B podaje pewną część klucza do wiadomości
publicznej. I przesyłka jest szyfrowana specjalnie dla
niej. Tu właśnie jest ta dodatkowa wymiana informacji
(nie "osobista" między A i B, ale jednak), o którą tak
się czepiałem.
To znaczy - nie mówię, żebym wszystko do końca
rozumiał:), ale przynajmniej nie ma paradoksu.

bo ja wiem, czy to nie miejsce na matematykę....:)))
Sprawa wygląda ciekawie. Tylko mała uwaga: czy faktycznie
wystarczy geniusz klasy Einsteina, żeby to złamać, czy
też niezawodność tego systemu (definiowana np. jako ilość
operacji niezbędnych do złamania szyfru) jest DOWIEDZIONA
matematycznie (wtedy żaden geniusz nie ma nic do gadania)?

pozdrawiam - Kopperek

PS Jeśli zacznę być zbyt upierdliwy, daj mi znać:).

[myslewiecjestem]

kopperek napisał:

> Aaaa, tak to ok!
>
> Czyli - B podaje pewną część klucza do wiadomości
> publicznej. I przesyłka jest szyfrowana specjalnie dla
> niej. Tu właśnie jest ta dodatkowa wymiana informacji
> (nie "osobista" między A i B, ale jednak), o którą tak
> się czepiałem.
> To znaczy - nie mówię, żebym wszystko do końca
> rozumiał:), ale przynajmniej nie ma paradoksu.
>
> bo ja wiem, czy to nie miejsce na matematykę....:)))
> Sprawa wygląda ciekawie. Tylko mała uwaga: czy faktycznie
> wystarczy geniusz klasy Einsteina, żeby to złamać, czy
> też niezawodność tego systemu (definiowana np. jako ilość
> operacji niezbędnych do złamania szyfru) jest DOWIEDZIONA
> matematycznie (wtedy żaden geniusz nie ma nic do gadania)?
>
> pozdrawiam - Kopperek
>
> PS Jeśli zacznę być zbyt upierdliwy, daj mi znać:).

Geniusz zawsze ma cos do gadania. Oto opowiesz o genialnym matematyku Gaussie.
Chcial zagiac ucznoiw i dac im cos do nieprzerobienia, by miec wiecej czsau dla
siebie. Kazal im dodac wszystkie liczby od 1 do 100. Sproboj, to zobaczysz
jakie to zadanie. Gauss po kilkunastu sekundach mial odpowiedz, czym oczywiscie
dobil swego profesora. Podobnie moze byc z kryptologia i naszym algorytmem nie
do zlamania. Jak Einstein powiedzial: regula na ten swiat jest z cala pewnoscia
PROSTA i PIEKNA. Tylko jak ja znalezc. OK, pomysl troche o zagadce Gaussa.
Daj mi znac kiedy mam Ci dac rozwiazanie. Oczywiscie rozwiazaniem nie jest suma
tylko sposob wymyslony przez Gaussa.
Nie nudzisz mnie.
Pozdr, Myslewiecjestem.

[Gość: pafcio]

najprostsz sposób to skorzystanie ze wzoru n*(n+1)/2, a najładniejsze do wzoru
logiczne dojście to zrozumienie że sumy liczb 1 i 100, 2 i 99, 3 i 98 itd są
takie same...

[kopperek]

myslewiecjestem napisał:

> Geniusz zawsze ma cos do gadania. Oto opowiesz o
genialnym matematyku Gaussie.
> Chcial zagiac ucznoiw i dac im cos do nieprzerobienia,
by miec wiecej czsau dla
>
> siebie. Kazal im dodac wszystkie liczby od 1 do 100.
Sproboj, to zobaczysz
> jakie to zadanie. Gauss po kilkunastu sekundach mial
odpowiedz, czym oczywiscie
> dobil swego profesora. Podobnie moze byc z kryptologia
i naszym algorytmem nie
> do zlamania. Jak Einstein powiedzial: regula na ten
swiat jest z cala pewnoscia
>
> PROSTA i PIEKNA. Tylko jak ja znalezc. OK, pomysl
troche o zagadce Gaussa.
> Daj mi znac kiedy mam Ci dac rozwiazanie. Oczywiscie
rozwiazaniem nie jest suma
> tylko sposob wymyslony przez Gaussa.
> Nie nudzisz mnie.
> Pozdr, Myslewiecjestem.

witam

No to schodzimy do pryncypiów:). Być moze nie do końca
precyzyjnie się wyraziłem: są problemy, których rozwiązać
nie potrafimy (jak dotąd) i takie, co do których
dowiedziono, że są niewykonalne. Przy pierwszym geniusz
oczywiście może wszystko przewrócić do góry nogami, w
obliczu drugiego jest bazradny. Pytanie - czy
odnalezienie algorytmu, pozwalającego na złamanie tego
klucza przy złożonosci obliczeniowej mniejszej niż
wykładnicza, jest NIEMOŻLIWE czy tylko nikt tego nie
zrobił. Inaczej - nie wiemy, jak to zrobić, czy wiemy, że
się nie da? To jest BARDZO istotna różnica.
Oczywiście - należy dla porządku wspomnieć o takiej
możliwości, że dowód istnieje i jest powszechnie
uznawany, a jednak tkwi w nim błąd; zatem w poprzednim
pytaniu można dodać - jak to jest wg dzisiejszej matematyki.
Historyjkę z Gaussem znam od dosyć dawna:), ale nigdy
mnie ona nie przekonywała jako dowód jego geniuszu - ten
akurat problem jest dziecinnie (dosłownie) prosty. To
oczywiście nie jest z mojej strony polemika.

pozdrawiam - Kopperek

[mesquaki]

kopperek napisał:

> Tylko mała uwaga: czy faktycznie
> wystarczy geniusz klasy Einsteina, żeby to złamać, czy
> też niezawodność tego systemu (definiowana np. jako ilość
> operacji niezbędnych do złamania szyfru) jest DOWIEDZIONA
> matematycznie (wtedy żaden geniusz nie ma nic do gadania)?
>

Z tego co wiem, w uproszczeniu klucze publiczne są generowane przez pomnożenie
przez siebie bardzo dużych liczb pierwszych.
Problem rozszyfrowania klucza prywatnego sprowadza się do rozłożenia powstałej
liczby na czynniki pierwsze i nie jest niemożliwy a tylko intensywny
komputacyjnie. Bezpieczeństwo systemu zależy od rozmiaru użytych kluczy.
Czy może coś pokręciłam? :)
pozdrawiam
mes

[myslewiecjestem]

mesquaki napisała:

> kopperek napisał:
>
> > Tylko mała uwaga: czy faktycznie
> > wystarczy geniusz klasy Einsteina, żeby to złamać, czy
> > też niezawodność tego systemu (definiowana np. jako ilość
> > operacji niezbędnych do złamania szyfru) jest DOWIEDZIONA
> > matematycznie (wtedy żaden geniusz nie ma nic do gadania)?
> >
>
> Z tego co wiem, w uproszczeniu klucze publiczne są generowane przez
pomnożenie
> przez siebie bardzo dużych liczb pierwszych.
> Problem rozszyfrowania klucza prywatnego sprowadza się do rozłożenia
powstałej
> liczby na czynniki pierwsze i nie jest niemożliwy a tylko intensywny
> komputacyjnie. Bezpieczeństwo systemu zależy od rozmiaru użytych kluczy.
> Czy może coś pokręciłam? :)
> pozdrawiam
> mes

Jest dokladnie tak jak mowisz.
Pozdr, Myslewiecjestem.

[kopperek]

mesquaki napisała:

> kopperek napisał:
>
> > Tylko mała uwaga: czy faktycznie
> > wystarczy geniusz klasy Einsteina, żeby to złamać, czy
> > też niezawodność tego systemu (definiowana np. jako ilość
> > operacji niezbędnych do złamania szyfru) jest DOWIEDZIONA
> > matematycznie (wtedy żaden geniusz nie ma nic do
gadania)?
> >
>
> Z tego co wiem, w uproszczeniu klucze publiczne są
generowane przez pomnożenie
> przez siebie bardzo dużych liczb pierwszych.
> Problem rozszyfrowania klucza prywatnego sprowadza się
do rozłożenia powstałej
> liczby na czynniki pierwsze i nie jest niemożliwy a
tylko intensywny
> komputacyjnie. Bezpieczeństwo systemu zależy od
rozmiaru użytych kluczy.
> Czy może coś pokręciłam? :)
> pozdrawiam
> mes

Dokładnie tak podejrzewałem (problem rozwiązywalny, ale
złożony).

Kopperek

Ps Mes - miło widzieć:)