Seminaria Sekcji Kryptologii i Ochrony Informacji

Uprzejmie informujemy, ze seminarium kryptologiczne w IMPAN 
odbywa sie w piatki, o godzinie 16 
w sali 106 na I pietrze Instytutu Matematycznego PAN
przy ul Sniadeckich 8.  Program seminarium obejmie m. innymi:
zagadnienia zwiazane z kryptoanaliza funkcji skrotu, algebraicznymi metodami 
kryptoanalizy, zastosowaniem funkcji eliptycznych w kryptografii oraz 
konstrukcja szyfrow asymetrycznych.

Zbigniew Jelonek
Janusz Szmidt
Aleksander Wittlin

SPIS REFERATÓW
ROK 2013/14
29.11.2013Aleksander WittlinBitcoin - wirtualny środek płatniczy
08.11.2013Janusz SzmidtKonstrukcja nieliniowych rejestrów przesuwnych
25.10.2013Jakub DerbiszStruktury dostępu i kryptosystemy oparte na krzywych eliptycznych (Omówienie III części pracy doktorskiej)
18.10.2013Jakub DerbiszStruktury dostępu i kryptosystemy oparte na krzywych eliptycznych (Omówienie II części pracy doktorskiej)
11.10.2013Jakub DerbiszStruktury dostępu i kryptosystemy oparte na krzywych eliptycznych (Omówienie I części pracy doktorskiej)
ROK 2012/13
26.04.2013Robert DryłoWstęp do kryptografii na krzywych eliptycznych - c.d.
19.04.2013Robert DryłoWstęp do kryptografii na krzywych eliptycznych - c.d.
15.03.2013Robert DryłoWstęp do kryptografii na krzywych eliptycznych - c.d.
08.03.2013Robert DryłoWstęp do kryptografii na krzywych eliptycznych - c.d.
18.01.2013Robert DryłoWstęp do kryptografii na krzywych eliptycznych - c.d.
14.12.2012
godz. 16.00
Michał StaromiejskiWielomianowe algorytmy sprawdzania lokalności pierścieni skończonych - c.d.
07.12.2012Jan BuryKomórka deszyfrażu Służby Bezpieczeństwa MSW Polski Ludowej - wyzwania i osiągnięcia - wspólne z Katedrą Informatyki i Ekonometrii WNP-SNS UKSW
30.11.2012
godz. 15.30
Michał StaromiejskiWielomianowe algorytmy sprawdzania lokalności pierścieni skończonych
23.11.2012 Zbigniew JelonekWstęp do kryptografii na krzywych eliptycznych (II)
09.11.2012 Zbigniew JelonekWstęp do kryptografii na krzywych eliptycznych (I)
12.10.2012 Zbigniew JelonekNowy szyfr symetryczny
ROK 2011/12
25.05.2012 Robert DryłoKonstruowanie krzywych genusu 2 z małymi stopniami zanurzeniowymi
30.03.2012Robert DryłoObliczanie rzędu krzywych genusu 2 o rozkładalnych jakobianach
24.02.2012Janusz SzmidtNieliniowe rejestry przesuwne
25.11.2011Zbigniew JelonekNowy algorytm symetryczny oparty na teorii krat
04.11.2011Janusz SzmidtKryptografia oparta na teorii krat
07.10.2011Stefan DziembowskiPrzegląd najnowszych rezultatów w teorii kryptografii odpornej na wycieki
ROK 2010/11
27.05.2011Nicolas T. CourtoisSecurity Evaluation of GOST 28147-89 in view of International Standardisation
29.04.2011Janusz SzmidtKryptoanaliza strukturalna sieci SPN - c.d.
15.04.2011Janusz SzmidtKryptoanaliza strukturalna sieci SPN
01.04.2011Jacek MarciniakStruktura i własności kryptograficznej funkcji skrótu CubeHash - c.d.
18.03.2011Robert DryłoMetoda mnożeń zespolonych dla krzywych eliptycznych
28.01.2011Jacek MarciniakStruktura i własności kryptograficznej funkcji skrótu CubeHash
14.01.2011Vasyl UstimenkoGraphs, geometrical codes and cryptographical algorithms
03.12.2010Tomasz LenarcikFormy kwadratowe a grupa klas ciała kwadratowego (II)
19.11.2010Tomasz LenarcikFormy kwadratowe a grupa klas ciała kwadratowego
05.11.2010Jerzy BrowkinTeoria Gaussa binarnych form kwadratowych (II)
22.10.2010Jerzy BrowkinTeoria Gaussa binarnych form kwadratowych (I)
ROK 2009/10
28.05.2010Robert DryłoKonstruowanie krzywych hipereliptycznych genusu 2 z małym stopniem zanurzeniowym - c.d.
07.05.2010Robert DryłoKonstruowanie krzywych hipereliptycznych genusu 2 z małym stopniem zanurzeniowym
23.04.2010Janusz SzmidtAtak na algorytm Trivium metodą kostek i testy kwadratowości
09.04.2010Robert DryłoKonstruowanie rodzin krzywych eliptycznych z małym stopniem zanurzeniowym
12.03.2010Robert DryłoAlgorytm Schoofa - c.d.
26.02.2010Robert DryłoAlgorytm Schoofa
29.01.2010Jerzy BrowkinKrzywe eliptyczne nad ciałami skończonymi a teoria grafów (na podstawie prac G. Musikera) - c.d.
22.01.2010Jerzy BrowkinKrzywe eliptyczne nad ciałami skończonymi a teoria grafów (na podstawie prac G. Musikera)
18.12.2009Tomasz LenarcikAlgorytm AKS testowania pierwszości liczb naturalnych
04.12.2009Jerzy BrowkinRóżne rodzaje liczb pseudopierwszych a rozkładanie na czynniki liczb naturalnych
20.11.2009Tomasz LenarcikFaktoryzacja wielomianów nad ciałem skończonym
06.11.2009Zbigniew JelonekAlgorytm Lenstry znajdowania bazy normalnej w ciele skończonym - c.d.
23.10.2009Christian RechbergerRebound Attacks and the SHA-3 Competition
09.10.2009Zbigniew JelonekAlgorytm Lenstry znajdowania bazy normalnej w ciele skończonym
ROK 2008/09
08.05.2009Robert DryłoConstructing pairing-friendly elliptic curves
27.03.2009Zbigniew JelonekO rozwiązywaniu równań wielomianowych
16.01.2009Janusz SzmidtAtak algebraiczny metodą kostek sześciennych
21.11.2008Robert DryłoPairing friendly elliptic curves (II)
07.11.2008Robert DryłoPairing friendly elliptic curves
24.10.2008Marcin KontakFunkcja skrótu MD6
10.10.2008Jerzy BrowkinAtak metodą kostek na kryptosystemy wielomianowe (według I. Dinura i A. Shamira)
ROK 2007/08
09.05.2008Jerzy BrowkinWulkany, krzywe eliptyczne i kryptografia
25.04.2008Jerzy MyckaRzeczywiste funkcje rekurencyjne - model obliczalności na liczbach rzeczywistych z przejściem granicznym i równaniami różniczkowymi
11.04.2008Janusz SzmidtKryptoanaliza funkcji skrótu GOST - c.d.
07.03.2008Janusz SzmidtSpecyfikacja algorytmu Advanced Encryption Standard
18.01.2008Zbigniew JelonekNowa metoda rozwiązywania układu równań wielomianów nad dowolnym ciałem
04.01.2008Małgorzata KupieckaAlgorytm Radduma-Semaeva rozwiązywania nieliniowych układów równań nad GF(q)
07.12.2007Zbigniew JelonekJak "klasycznie" rozwiązać system równań wielomianowych?
23.11.2007Robert DryłoKonstruowanie krzywych eliptycznych o zadanym rzędzie (III)
09.11.2007Robert DryłoKonstruowanie krzywych eliptycznych o zadanym rzędzie (II)
19.10.2007Robert DryłoNowy algorytm generowania krzywych eliptycznych o zadanej randze
ROK 2006/07
20.06.2007Nicolas T. CourtoisPractical Algebraic Cryptanalysis of Block Ciphers
18.05.2007Jerzy BrowkinAlgorytm F5 dla wyznaczania baz Groebnera
20.04.2007Krystian MatusiewiczKryptoanaliza FORK-256 i uwagi na temat stanu badań nad funkcjami skrótu
20.04.2007Jacques PatarinGeneric Attacks and Proofs of Security for the Xor of Random Permutations
13.04.2007Jerzy BrowkinBazy Groebnera (III)
30.03.2007Tomasz WitkowskiProblem spełnialności i kryptoanaliza logiczna
23.03.2007Ewa SytaZastosowanie dowodów o wiedzy zerowej w procesie uwierzytelniania
09.03.2007Janusz SzmidtKryptoanaliza funkcji skrótu
02.03.2007Jerzy BrowkinBazy Groebnera (II)
23.02.2007Jerzy BrowkinBazy Groebnera (I)
ROK 2005/06
24.11.2005Jacek PomykałaCyfrowy podpis pełnomocniczy
ROK 2004/05
28.04.2005Marcin BronowskiKryptoanaliza szyfru blokowego SKIPJACK metodą różniczek niemożliwych
14.04.2005Daniel NapiórkowskiEfektywna implementacja arytmetyki na krzywej eliptycznej
07.04.2005Aneta SuchaneckaKryptoanaliza funkcji skrótu Haval
17.03.2005Marcin DawiecKryptoanaliza algorytmów stosowanych w systemie GSM
14.01.2005Nigel SmartRevisiting the relationship between DLP and DHP for elliptic curves
18.11.2004Stefan DziembowskiO protokołach PIR i ich zastosowaniu w badaniach teorii wiecznego bezpieczeństwa
16.09.2004Eli BihamInstant Ciphertext-only Cryptoanalysis of GSM Encrypted Communication
15.09.2004Eli BihamNew results on SHA-0 and SHA-1
ROK 2003/04
20.05.2004Stefan DziembowskiWprowadzenie do obliczeń wielopodmiotowych
13.05.2004Joanna ChmielKryptograficzne funkcje skrótu - metody ataku
22.04.2004Remigiusz CzerwińskiBadanie implementacji algorytmu MISTY w strukturach programowalnych
01.04.2004Adam DudzińskiSchemat podpisu cyfrowego QUARTZ i jego implementacja
25.03.2004Michał MisztalBłyskawiczna kryptoanaliza z samym szyfrogramem komunikacji szyfrowanej w systemie GSM
18.03.2004Bartosz ŻółtakFunkcja jednokierunkowa i szyfr strumieniowy VMPC
11.03.2004Bartosz ŹrałekLiczby Carmichaela w problemach rozkładu i rozkładalności
04.03.2004Sławomir BarabaszProgowe Schematy Podpisu - pomysły i przykłady realizacji
26.02.2004Ewa RozwencFunkcje Bent. Normalne funkcje bent i rozszerzenia normalne
15.01.2004Aneta ZwierkoSystem mikropłatności MINX
18.12.2003Michał MisztalStrategia szerokiej ścieżki w projektowaniu algorytmów blokowych
11.12.2003Kamil KuleszaProtokoły bezpieczeństwa budowane przy pomocy teorii grafów
04.12.2003Marcin Kontak i Janusz SzmidtKryptoanaliza funkcji skrótu
27.11.2003Marcin Kontak i Janusz SzmidtSpecyfikacja jednokierunkowych funkcji skrótu
30.10.2003Jacek PomykałaProblemy faktoryzacji i pierwszości - dalekie czy bliskie
23.10.2003Andrzej ChmielowiecZliczanie punktów krzywej eliptycznej nad ciałem skończonym charakterystyki 2 - rozszerzenie algorytmu Satoh
16.10.2003Michał MisztalMetody kryptoanalizy szyfrów blokowych
10.10.2003Kazimierz RzążewskiOd mechaniki kwantowej do inżynierii i informatyki kwantowej
ROK 2002/03
17.01.2003Jacques PatarinAlgebraic attacks on symmetric ciphers
10.01.2003Jacques PatarinAbout the XL algorithm over GF(2) (praca wykonana wspólnie z Nicolas Courtois)
ROK 2001/02
07.06.2002Kamil KuleszaOn graph coloring check-digit method
24.05.2002Agata FraneckaElektroniczne pieniądze - wybrane protokoły
10.05.2002Mariusz SkałbaRozkłady pewnych liczb pseudopierwszych na czynniki
12.04.2002Jerzy BrowkinLiczby pseudopierwsze Frobeniusa - c.d.
05.04.2002Jerzy BrowkinLiczby pseudopierwsze Frobeniusa
22.03.2002Maciej KwiatkowskiProtokół anonimowych mikropłatności
15.03.2002Tomasz KijkoBadanie i generacja funkcji boolowskich o odpowiednich własnościach kryptograficznych
08.03.2002Krzysztof MańkKontrola klucza w algorytmach kolektywnego generowania klucza
01.03.2002Michał MisztalKryptoanaliza różnicowa szyfru Q
22.02.2002Jerzy BrowkinZnajdowanie logarytmu dyskretnego o znanej liczbie jedynek w przedstawieniu binarnym
25.01.2002Boris RyabkoThe simple ideal cipher system
16.01.2002Jacques PatarinProofs of Security on Feistel Schemes (i.e. on encryption schemes in cryptography)
11.01.2002Jacques PatarinGeneric Attacks on Feistel Schemes
14.12.2001Rafał NesselKryptosystem NTRU
30.11.2001Marek KuśKryptografia kwantowa

dr Janusz Szmidt

Nonlinear feedback shift registers (NLFSRs) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of linear feedback shift registers (LFSRs). In general, it is not known how to construct all NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. Advanced technology of parallel computing has been applied both in software and hardware to search for maximum period NLFSRs having a fairly simple algebraic normal form. It is presented a theorem how to construct all NLFSRs of given order having one of them, e.g. LFSR one by applying the cross-join method.


dr Jan Bury

W referacie przedstawiona zostanie historia oraz działania komórki deszyfrażu należącej do Biura "A" MSW PRL. Przeanalizowane zostaną najważniejsze typy operacji, w których była wykorzystywana, oraz osiągnięte rezultaty w kryptoanalizie obcych kodów i szyfrów.


dr Michał Staromiejski

Przedstawię prostą charakteryzację skończonych algebr lokalnych nad ciałami (skończonymi) z zastosowaniem do sprawdzania lokalności pierścieni skończonych. Przedyskutuję wielomianowy, deterministyczny algorytm sprawdzania czy algebra, dana za pomocą tzw. reprezentacji bazowej, jest lokalna. Stosując znany algorytm deterministyczny dla testowania pierwszości, przedstawię również deterministyczny algorytm sprawdzający lokalność dowolnych pierścieni skończonych i przedyskutuję warianty randomizowane obu algorytmów.


prof. dr hab. Zbigniew Jelonek

GOST 28147-89 is is a well-known 256-bit block cipher which is a plausible alternative for AES-256 and triple DES, which however has a much lower implementation cost. GOST is implemented in standard crypto libraries such as OpenSSL and Crypto++ and is increasingly popular and used also outside its country of origin and on the Internet. In 2010 GOST was submitted to ISO, to become a worldwide industrial encryption standard. Until 2011 researchers unanimously agreed that GOST could or should be very secure, which was summarized in 2010 in these words: despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken". As of today ISO is still in the process of standardising GOST. and it seems that never in history of industrial standardisation ISO had such a strong submission in terms of implementation cost vs. the the very high security level claimed for GOST. Unhappily however it was recently discovered that GOST can be broken. One simple attack was already presented in February at FSE 2011. In this talk we are going to present another attack which requires much less memory, and doesn't even require the reflection property to hold, without which the recent attack from FSE 2011 wouldn't work. We will also make a few remarks about much better yet unpublished attacks on GOST.


dr Robert Dryło

Krzywe eliptyczne i jakobiany krzywych hipereliptycznych z małymi stopniami zanurzeniowymi stosujemy do implementacji protokołów opartych na iloczynach dwuliniowych. Podstawowym problemem jest skonstruowanie odpowiednich krzywych. Podczas referatu omówię uogólnienia metod konstruowania krzywych eliptycznych na krzywe hipereliptyczne genusu 2.


dr Robert Dryło

Wiadomo, że ogólne metody obliczania rzędu krzywych hipereliptycznych są zbyt wolne w praktyce. Efektywniejsze metody istnieją dla krzywych o rozkładalnych jakobianach. Na przykład, Satoh podał metodę obliczania rzędu krzywych y2=x5+ax3+bx. W kryptografii możemy stosować krzywe hipereliptyczne C/Fq takie, że Jac(C) jest prosty nad Fq, ale jest izogeniczny z produktem krzywych eliptycznych nad pewnym rozszerzeniem Fq. Podczas referatu omówię metodę obliczania rzędu jakobianu takich krzywych.


dr Janusz Szmidt

NFSR (Nonlinear Feedback Shift Registers) mają podstawowe zastosowania w konstrukcji szyfrów strumieniowych. Podstawowymi problemami w teorii NFSR jest określenie okresowości i złożoności liniowej NFSR. Zagadnienie oszacowania z dołu złożoności liniowej NFSR związane jest z istnieniem rozwiązań układów równań diofantycznych w ciałach skończonych.


dr Janusz Szmidt

Omówię następujące zagadnienia:

Referat ma charakter popularnonaukowy.
dr Stefan Dziembowski

Fizyczne implementacje systemów kryptograficznych podatne są na ataki typu side-channel. W ostatnich latach pojawiły się liczne teoretyczne metody zapobiegania takim atakom. W referacie dokonamy przeglądu tych metod.


prof. Nicolas T. Courtois

GOST 28147-89 is is a well-known 256-bit block cipher which is a plausible alternative for AES-256 and triple DES, which however has a much lower implementation cost. GOST is implemented in standard crypto libraries such as OpenSSL and Crypto++ and is increasingly popular and used also outside its country of origin and on the Internet. In 2010 GOST was submitted to ISO, to become a worldwide industrial encryption standard. Until 2011 researchers unanimously agreed that GOST could or should be very secure, which was summarized in 2010 in these words: "despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken".
As of today ISO is still in the process of standardising GOST. and it seems that never in history of industrial standardisation ISO had such a strong submission in terms of implementation cost vs. the the very high security level claimed for GOST. Unhappily however it was recently discovered that GOST can be broken. One simple attack was already presented in February at FSE 2011. In this talk we are going to present another attack which requires much less memory, and doesn't even require the reflection property to hold, without which the recent attack from FSE 2011 wouldn't work. We will also make a few remarks about much better yet unpublished attacks on GOST.


dr Janusz Szmidt

Referowana będzie praca A. Biryukov, A. Shamir, Structural cryptanalysis of SASAS (Journal of Cryptology 23 (2010), 505–518). Jest to atak, którego celem jest odzyskanie nieznanej struktury szyfru blokowego typu sieć podstawieniowo-przestawieniowa, np. dla zredukowanej wersji algorytmu AES.


dr Robert Dryło

Metoda mnożeń zespolonych jest stosowana do konstruowania krzywych eliptycznych nad ciałami skończonymi. Omówię matematyczne podstawy tej metody oraz zastosowania do rozwiązania następujacych dwóch problemów:

  1. Konstruowania krzywych eliptycznych rzędu prawie pierwszego nad danym ciałem skończonym.
  2. Konstruowania krzywych eliptycznych o danym rzędzie nad pewnym ciałem skończonym.


prof. Vasyl Ustimenko

We will use the interpretation of Incidence geometries to create fast algorithms to measure the distance between vertices of distance regular graphs of Lie type and related to them Hemmeter and Ustimenko graphs, double Grassman graphs. Distance regular graphs of Coxeter and Lie type are important examples of graphs for which there is the algorithms to measure the distance between vertices which is much faster than the speed of well known Dijkstra method. We will also use the flag systems of Lie geometries for the generation of polynomial public keys protected by the complexity of group theoretical discrete logarithm problems as well as incidence graph based key-exchange protocols.


dr Robert Dryło

Będziemy zajmować się konstruowaniem krzywych, których jakobian zawiera podgrupę dużego rzędu pierwszego z małym stopniem zanurzeniowym. Takie jakobiany są wykorzystywane do implementacji protokołów opartych na iloczynach Weila lub Tate. Losowy wybór krzywej o takich własnościach jest bardzo mało prawdopodobny. Podczas referatu podam nową metodę generowania takich krzywych o genusie 2, która jest oparta na twierdzeniu Hondy-Tate o reprezentacji klas isogenii rozmaitości abelowych przez liczby q-Weila.


dr Robert Dryło

Krzywe eliptyczne z małym stopniem zanurzeniowym stosuje się do implementacji pewnych protokołów (np. krótkich podpisów cyfrowych). Takie krzywe muszą być specjalnie konstruowane, ponieważ występują bardzo rzadko. Szczególną uwagę zwraca się na to, aby rząd podgrupy używanej do kodowania był jak najbliższy rzędowi krzywej, co poprawia efektywność. Krzywe o takich własnościach na ogół łatwiej otrzymywać przy pomocy tzw. rodzin (tzn. wielomianów, których wartości przypuszczalnie na nieskończenie wielu liczbach całkowitych dają parametry krzywych, które następnie można efektywnie skonstruować). Ogólne metody konstruowania zostały rozwinięte tylko dla tzw. rodzin zupełnych. Nie zostały również podane ogólne metody konstruowania rodzin krzywych, których rząd jest prawie pierwszy.

Podczas referatu skupię się na problemach konstruowania:
(i) rodzin dowolnego typu,
(ii) rodzin krzywych, których rząd jest prawie pierwszy.

Przedstawię dwie metody konstruowania rodzin (i). Ponadto podam opis rodzin (ii) pozwalający otrzymać układy równań, których rozwiązania wymierne wyznaczają takie rodziny.


prof. Jerzy Browkin

  1. Omówienie rozwiązań zadań domowych sformułowanych na seminarium w dniu 22 stycznia.
  2. Referat na temat analogii między grupami punktów wymiernych na krzywych eliptycznych nad ciałami skończonymi a grupami krytycznymi grafów kołowych.
Po Seminarium jestem gotów przedstawić osobom zainteresowanym kilka problemów badawczych związanych z pracami Musikera.


prof. Jerzy Browkin

G. Musiker z powodzeniem zbudował pewne grafy, które dają takie same grupy, jak grupy punktów wymiernych na krzywych eliptycznych określonych nad ciałami skończonymi, lecz nie odwoływał się do tych krzywych. Zamierzam omówić kilka spraw poruszanych w tych pracach.


prof. Jerzy Browkin

Nawiązując do ostatniego referatu Prof. Jelonka zastosujemy podobne metody do liczb całkowitych zamiast do wielomianów nad ciałem skończonym. Badamy rozkładalność liczby n postepując analogicznie:

Wybieramy dowolnie liczbę a względnie pierwszą z n. Jeżeli an-1 nie przystaje do 1 modulo n, to liczba n jest złożona na mocy małego twierdzenia Fermata.

Niech więc an-1 daje resztę 1 modulo n. Podnosimy a do potęgi (n-1)/2 modulo n. Jeżeli otrzymamy 1 lub -1, to wybieramy inną liczbę a. Jeżeli otrzymamy liczbę b różną od 1 i -1, to obliczamy NWD(n,b-1) oraz NWD(n,b+1). Jedna z tych liczb jest właściwym dzielnikiem liczby n.

Omówię różne modyfikacje tego algorytmu. Szczegóły można znaleźć w  mojej pracy w Mathematics of Computation 73 (2004), 1031-1037, errata ibid. 74 (2005), p. 1573.


dr Robert Dryło

Krzywe eliptyczne odpowiednie dla zastosowań w "Pairing-based cryptography" są bardzo rzadkie, dlatego poszukuje się metod konstruowania ich. Takie metody dają albo pojedyncze krzywe, albo rodziny krzywych. Na ogół w drugim przypadku można otrzymać krzywe o lepszych własnościach.

Omówię podstawowe własności krzywych, które są istotne dla "Pairing-based cryptography", oraz metody konstruowania rodzin takich krzywych.


prof. Zbigniew Jelonek
Pokażę, że metoda, którą opisałem na poprzednich seminariach jako pracującą w charakterystyce 0, pracuje też w dowolnej charakterystyce. W szczególnosci pokażę, jak efektywnie obliczyć zero automorfizmu wielomianowego F:kn→kn w dowolnej charakterystyce.
dr Janusz Szmidt (WAT)

Referat będzie dotyczył pracy Dinura i Shamira Cube attacks on tweakable black box polynomials. W szczególności przedstawiony będzie atak na szyfr strumieniowy Trivium.


dr Robert Dryło

Omówię protokoły implementowane na takich krzywych, np. uzgadniania klucza publicznego między trzema osobami w jednej rundzie, podpisu cyfrowego czy idee realizacji systemu, w którym autentyczność klucza sprawdza się przy pomocy tożsamości jego właściciela. Przedstawię również metody konstruowania takich krzywych, które są ważne choćby z takiego powodu, że losowo wybrana krzywa nie nadaje się do tego typu zastosowań.


Marcin Kontak (WAT)

Przedstawię prezentację Ronalda Rivesta z ostatniego Crypto na temat nowej funkcji skrótu MD6. Ponieważ był to wykład zaproszony (tzw. Invited Talk), dlatego nie ma go w materiałach z konferencji, co trochę utrudnia jego całkowite zrozumienie. Seminarium poprowadzę jedynie na podstawie slajdów Rivesta i tego, co usłyszałem na wykładzie na Crypto, wobec czego może to nie być do końca zrozumiałe (szczególnie, że sam nie wszystko z tych slajdów zrozumiałem).


profesor Jerzy Browkin (IM PAN)

Niech E będzie krzywą eliptyczną określoną nad ciałem skończonym F i niech m będzie rzędem grupy E(F) punktów na tej krzywej o współrzędnych w F. Z punktu widzenia kryptografii byłoby dobrze, gdyby ta grupa była cykliczna, jednak grupa abelowa rzędu m może cykliczna nie być.

Jak wiadomo, przy dowolnej izogenii E→E' rząd grupy się nie zmienia, a struktura grupy może ulec zmianie. Szukamy więc takiej izogenii, aby grupa E'(F) była cykliczna.

Zamierzam mówić dokładniej na ten temat. Dla poglądowego przedstawienia tych spraw wygodnie jest narysować odpowiedni wulkan, czego niestety w tym streszczeniu zrobić nie mogę.


Jerzy Mycka z Instytutu Matematyki UMCS

Referat będzie poświęcony nowemu podejściu do zagadnień obliczalności na liczbach rzeczywistych. Wprowadzona zostanie nowa klasy rzeczywistych funkcji rekurencyjnych określona za pomocą definicji indukcyjnej wykorzystującej przejście graniczne oraz rekursję różniczkową. Podane zostaną dodatkowe warunki nałożone na klasę zapewniające poprawność definicji i użyteczność zdefiniowanej klasy funkcji.

Na bazie powyżej wspomnianej definicji przedstawione zostaną podstawowe własności rzeczywistych funkcji rekurencyjnych. Najpierw podane zostaną przykłady oraz alternatywne metody wprowadzenia tej klasy. Następnie wskazane zostaną ograniczenia związane z rozstrzygalnością oraz związki z klasyczną teorią złożoności obliczeniowej. Ponadto zostanie krótko omówiony aspekt fizycznej realizowalności wprowadzonego modelu obliczeń.

Jako główne zagadnienie referatu zostanie wyeksponowany związek rzeczywistych funkcji rekurencyjnych z hierarchią arytmetyczną oraz problem istnienia funkcji uniwersalnej w tym modelu. Na tej podstawie zostanie udowodniony nieskończonych charakter hierarchii rzeczywistych funkcji rekurencyjnych zbudowanej ze względu na operator przejścia granicznego. Dodane zostaną także informacje o iterowalności w obrębie modelu oraz związkach z funkcjonałami rekurencyjnymi. Na koniec wskazane zostaną dalsze kierunki badań.


Małgorzata Kupiecka (WAT)

Algorytm autorstwa Havarda Raduma i Igora Semaeva to jedna z najnowszych metod rozwiązywania nieliniowych układów równań nad ciałami skończonymi. Rozwiązywanie takich układów to kluczowa część ataków algebraicznych. Algorytm opiera się na zaskakująco prostym pomyśle - jego podstawowym krokiem jest eliminowanie rozwiązań niemożliwych. Warunkiem jego efektywości jest rzadkość układu w sensie małej liczby zmiennych występujących w jednym równaniu. Jest to jedyny ze znanych dotychczas algorytmów, którego złożoność nie zależy od stopnia równań. W referacie omówiona zostanie podstawowa wersja algorytmu oraz kilka pomysłów na jego usprawnienie.


prof. Zbigniew Jelonek (IMPAN)

Pokażę ogólny algorytm rozwiązujący układ wielomianowych równań (nad dowolnym ciałem). Moja metoda jest oparta na klasycznej metodzie eliminacji i jest różna od metod opartych na bazach Groebnera.


dr Nicolas T. Courtois (University College of London)

In 2001 Courtois and Pieprzyk have conjectured that though for dense systems the problem is NP-hard, many systems of sparse multivariate quadratic equations can be solved in practice. This allows to design algebraic attacks on block ciphers. In 2006 it was discovered that not only many systems of equations can be solved by Gröbner bases, which nobody have noticed before, but also sometimes by much simpler algorithms such as ElimLin. Moreover a new very fast method was proposed by Courtois and Bard: conversion and usage of SAT solvers.The possibility of efficiently solving sparse polynomial equations opens many avenues for future research. In 2007 Courtois and Bard broke KeeLoq, a block cipher used by millions of people worldwide to unlock their car doors and alarms. This is the first time in history that a full-size industrial block cipher was broken by an algebraic attack. When looking at limitations of algebraic attacks we realize that some are very strong (we hit the wall when the number of rounds increases) and some are spectacularly naive (such as the degree in Gröbner basis computation).


Jerzy Browkin

Omówię pracę dyplomową T. Stegersa na temat algorytmu F5 zaproponowanego przez J. C. Faugère'a. Jest to algorytm mający usprawnić wyznaczanie bazy Groebnera ideału generowanego przez dane wielomiany. Niestety, nie zawsze działa on dobrze.

Będę zakładał znajomość algorytmu Buchbergera, którego nie omawiałem przy tablicy, lecz jest on opisany wraz z dowodem w moim tekście o bazach Groebnera.


Krystian Matusiewicz (Macquarie University)

W pierwszej części seminarium przedstawiona zostanie kryptoanaliza zaproponowanej na FSE'2006 dedykowanej funkcji skrótu FORK-256. Pokaże ona, jak wykorzystując pewną szczególną słabość pojedynczej rundy w funkcji kompresji można otrzymać interesujące charakterystyki różnicowe dla jednego kroku, a następnie rozszerzyć je do ścieżek różnicowych dla całej funkcji. Używając tej metody można znaleźć kolizje dla kompletnej funkcji kompresji ze złożonością obliczeniową 2126.6 używając tylko małej pamięci roboczej. Zaprezentowana metoda ataku jest praktyczna i pozwala na znajdowanie blisko-kolizji o wadze poniżej 30 na pojedynczym komputerze PC. Na zakończenie omówione zostanie teoretyczna optymalizacja która pozwala na obniżenie złożoności obliczeniowej do ok. 2110 kosztem użycia pamięci o rozmiarze rzędu 267 słów. Ponadto pokazana zostanie metoda rozszerzenia ataku z funkcji kompresji na funkcję skrótu. W drugiej części seminarium przedstawione zostanie kilka uwag na temat obecnego stanu badań w dziedzinie kryptograficznych funkcji skrótu w świetle zapowiadanego konkursu NIST na nową funkcję skrótu.


Jacques Patarin (Versailles)

Xoring the output of k permutations, k≥2, is a very simple way to construct pseudo-random functions from pseudo-random permutations. Moreover such constructions have many applications in cryptography. In this talk we will study the best known generic attacks on these constructions, and we will present the best security results obtained.


Ewa Syta

W ramach tematu postaram się omówić następujące zagadnienia:

  1. Uwierzytelnianie (definicja, założenia, najpopularniejsze rozwiązania)
  2. Idea i własności dowodów o wiedzy zerowej (definicja, cechy charakterystyczne, klasy problemów obliczeniowych)
  3. Zastosowanie teorii grafów (definicje: graf, cykl, cykl Hamiltona, problem znajdowania cykli Hamiltona, izomorfizm grafów)
  4. Algorytmy uwierzytelniające oparte o DWZ (podział, krótkie omówienie)


prof. Jerzy Browkin
    Bazy Groebnera to są bazy ideałów pierścienia wielomianów wielu
zmiennych. Bazy te mają różne dobre własności, których nie mają inne
bazy. Zamierzam przedstawić nastepujace sprawy:
    1. Definicja bazy Groebnera.
    2. Algorytm dzielenia wielomianów wielu zmienych, w szczególności
       dzielenie przez bazę Groebnera.
    3. Warunek Buchbergera na to, aby baza była bazą Groebnera.
    4. Algorytm Buchbergera dla wyznaczania bazy Groebnera.
    5. Baza Groebnera zredukowana.
    6. Modyfikacje algorytmu Buchbergera.

    OMÓWIENIE KOLEJNYCH PUNKTÓW
Ad 1. Do zdefiniowania bazy Groebnera trzeba ustalić pewien dobry porządek 
w zbiorze jednomianów. Przedstawię więc takie porzadki, co pozwoli 
zdefiniować bazę Groebnera (zależną od porządku!) i udowodnić, że baza
Groebnera naprawdę jest bazą. Do tego celu będę też musiał podać 
podstawowe informacje o ideałach generowanych przez jednomiany.

Ad 2. Zwykły algorytm dzielenia wielomianu wielu zmiennych przez układ
wielomianów daje pewną resztę, ale ta reszta ma zupełnie przypadkowe 
własności. Na przykład zależy od kolejności wielomianów w tym układzie.
Natomiast dzielenie przez układ, który jest Bazą Groebnera, nie ma tych
wad, a ma szereg zalet.

Ad 3. Warunek Buchbergera pozwala rozstrzygnąć w skończonej liczbie 
kroków, czy dana baza ideału jest bazą Groebnera. Jest to bardzo pomysłowy 
warunek, który oprócz samych wielomianów z bazy wykorzystuje tzw. syzygie 
par tych wielomianów. Warunek Buchbergera mówi, że te syzygie mają dawać 
resztę 0 przy dzieleniu przez daną bazę.

Ad 4. Algorytm Buchbergera pozwala rozszerzyć dowolną bazę ideału do 
pewnej jego bazy Groebnera. Po prostu, gdy syzygia pewnej pary wielomianów 
nie daje reszty 0 przy dzieleniu przez tę bazę, to do bazy dołaczamy tę 
syzygię i tak aż do skutku.

Ad 5. Ideał ma na ogół wiele baz Groebnera, lecz jeśli nałożymy na nie 
odpowiednie warunki, to otrzymamy jednoznacznie określoną bazę Groebnera. 
Nazywa się ją bazą zredukowaną. Ta baza zredukowana jest najlepsza ze 
wszystkich.

Ad 6. Niestety algorytm Buchbergera omówiony w punkcie 4. jest zbyt 
skomplikowany algorytmicznie. Jest w nim trochę niepotrzebnych kroków.
Przedstawię kilka podstawowych modyfikacji oryginalnego algorytmu 
Buchbergera, które w wielu przypadkach mają zalety z algorytmicznego 
punktu widzenia.

    INNE INFORMACJE
    Nie zakładam u słuchaczy żadnych specjalnych wiadomości. Wystarczy 
wiedzieć, co to jest wielomian wielu zmiennych (o współczynnikach 
w jakimś ciele) i co to jest ideał pierścienia wielomianów.
    Nie podaję żadnych informacji na temat literatury przedmiotu. Jest 
bardzo dużo różnych opracowan tej tematyki i trudno wyróżnić jakiś 
podręcznik. Najlepiej szukać przez GOOGLE pod hasłem "Groebner basis"
i otrzyma się dziesiątki albo i setki pozycji.
    Postaram się mówić bez pośpiechu i zrozumiale. Tematyka wydaje się 
interesująca z matematycznego punktu widzenia i nie wymaga reklamy.

doc. dr  hab. Jacek Pomykała z Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

Referat będzie poświęcony zastosowaniu schematu podziału sekretu wg Shamira do tzw. cyfrowego podpisu pełnomocniczego (ang. threshold proxy signature scheme). Planuję dokładniej omówić schemat takiego podpisu, którego bezpieczeństwo opiera się na problemie logarytmu dyskretnego w grupie punktów wymiernych krzywej eliptycznej nad ciałem skończonym.


Marcin Bronowski z WAT

Osią wykładu będzie opracowany przez NSA, jako tajny, algorytm SKIPJACK. Na podstawie historii jego powstawania i wdrażania omówiony zostanie problem tzw. "kryptografii kontrolowanej". Następnie przedstawiona będzie jego specyfikacja. Na zakończenie po krótkim wprowadzeniu w zagadnienia kryptoanalizy różnicowej pokazane zostaną ataki na SKIPJACKA wykorzystujące różniczki niemożliwe, a w szczególności atak na 25-rundowy wariant.


Daniel Napiórkowski z WAT

Zostanie przedstawiona krótka analiza złożoności obliczeniowej działań na grupie punktów krzywej eliptycznej. Szczególna uwaga poświęcona będzie efektywnym metodom obliczania wielokrotności punktu. Omówione zostanie również wykorzystanie działania połowienia punktu, jako jednego ze sposobów na przyspieszenie obliczeń.


Aneta Suchanecka z WAT

HAVAL jest kryptograficzną funkcją skrótu, której struktura jest podobna do innych powszechnie używanych funkcji, takich jak MD5 oraz SHA-1. Specyfikacja algorytmu HAVAL zawiera parametr bezpieczeństwa, liczbę rund, która może być wybrana między 3, 4 i 5. W świetle ostatnich doniesień o złamaniu SHA-1 i MD5 temat kryptoanalizy funkcji skrótu stał się bardzo popularny. Przedstawię praktyczny atak znajdowania kolizji dla 3-rundowej wersji funkcji skrótu HAVAL, który wykorzystuje podobne techniki jak ataki na inne funkcje z rodziny MD4.


We will look again at the method of Maurer/Wolf for showing equivalence between the DLP and DHP. We will concentrate on the case where the DHP is defined over an elliptic curve and show that a relatively tight security reduction can be found in all cases.


dr Stefan Dziembowski z Uniwersytetu Warszawskiego

Protokół Prywatnego Pozyskiwania Danych (ang.: Private Information Retrieval, PIR) jest wykonywany przez dwóch uczestników: klienta i bazę danych. Protokół ten pozwala klientowi uzyskać dostęp do bazy w taki sposób, by baza nie uzyskała żadnej informacji na temat zapytania zadanego przez klienta. Protokoły takie istnieją, o ile spełnione są założenia o trudności pewnych problemów obliczeniowych. Teoria wiecznego bezpieczeństwa (ang.: everlasting security) zajmuje się konstrukcją protokołów kryptograficznych, które są bezpieczne ,,na zawsze'' (np. szyfrowanie RSA z kluczem o długości 2048 prawdopodobnie nie spełnia tego warunku, gdyż prędzej czy później powstaną metody jego złamania).

Tematem referatu będzie wprowadzenie do obydwu zagadnień oraz pokazanie niespodziewanego związku między teorią PIR a teorią wiecznego bezpieczeństwa.

Referat jest oparty na pracy:
Stefan Dziembowski i Ueli Maurer On Generating the Initial Key in the Bounded-Storage Model, EUROCRYPT'04


prof. dr Eli Biham z Technion (Politechniki) w Haifie w Izraelu

In this talk we present a very practical ciphertext-only cryptanalysis of GSM encrypted communication, and various active attacks on the GSM protocols. These attacks can even break into GSM networks that use ``unbreakable'' ciphers. We describe a ciphertext-only attack on A5/2 that requires a few dozen milliseconds of encrypted off-the-air cellular conversation and finds the correct key in less than a second on a personal computer. We then extend this attack to a (more complex) ciphertext-only attack on A5/1. We describe new attacks on the protocols of networks that use A5/1, A5/3, or even GPRS. These attacks are based on security flaws of the GSM protocols, and work whenever the mobile phone supports A5/2. We emphasize that these attacks are on the protocols, and are thus applicable whenever the cellular phone supports a weak cipher, for instance they are also applicable using the cryptanalysis of A5/1. Unlike previous attacks on GSM that require unrealistic information, like long known plaintext periods, our attacks are very practical and do not require any knowledge of the content of the conversation. These attacks allow attackers to tap conversations and decrypt them either in real-time, or at any later time. We also show active attacks, such as call hijacking, altering of data messages and call theft.

Joint work with Elad Barkan and Nathan Keller
prof. dr Eli Biham z Technion (Politechniki) w Haifie w Izraelu

In this talk we present new techniques for finding collisions of variants of SHA-0 and SHA-1. These techniques allow to find collisions of (the full 80 rounds of) SHA-0 with a 2^56 complexity, and to find near-collisions of the full compression function of SHA-0 on a home PC. The strength of SHA-0 is shown not to be montoneous with the number of rounds. We use the very surprising fact that the messages have many neutral bits, some of which do not affect the differences for about 15-20 rounds. A method to use near-collisions as a tool in order to find collisions, which is especially useful in cases where the original technique cannot find collisions (such as 50-round SHA-0), will also be shown. These techniques were improved by Antoine Joux, who used them to find a collision of the full SHA-0. We then discuss the application of these techniques to SHA-1, and present collisions of reduced variants of SHA-1 (our current record is 36 rounds), along with near-collisions of longer variants.

Joint work with Rafi Chen
dr Stefan Dziembowski (Uniwersytet Warszawski)

Dokonamy wprowadzenia do obliczeń wielopodmiotowych (ang.: multiparty computations, MPC). Dziedzina ta została zapoczątkowana pracami [1,2] i była intensywnie rozwijana przez ostatnie dwie dekady. Nieformalnie, protokoły obliczeń wielopodmiotowych umożliwiają grupie użytkowników wykonanie wspólnego zadania bez wzajemnego ujawniania swoich sekretów. (Przykładem może być wspólne obliczenie publicznie znanej funkcji z zachowaniem tajności jej argumentów).

Przedstawione zostaną najważniejsze definicje, wyniki i kierunki badań. Nie jest wymagana żadna wcześniejsza znajomość tych zagadnień. Znajomość podstaw kryptografii może być przydatna.

  1. Goldreich, Micali and Wigderson. How to play any mental game, STOC 1987
  2. A. C. Yao. Protocols for secure computations, FOFS 1982.


Joanna Chmiel

Na seminarium przedstawione będą znane metody ataków (na podstawie między innymi monografii Barta Preneela Analysis and Design of Cryptographic Hash Functions) na funkcje skrótu, wraz z przykładami.


Michał Misztal

Zaprezentowano bardzo praktyczny atak z samym szyfrogramem na komunikację szyfrowaną w systemie GSM i różne aktywne ataki na protokoły GSM. Atak te mogą nawet włamywać się do sieci GSM, która używa szyfrów "nie do złamania". Opisano atak z samym szyfrogramem na A5/2, który wymaga tylko kilkunastu milisekund szyfrowanej off-the-air rozmowy i znajduje poprawny klucz w mniej niż sekundę na PC. Rozszerzono ten atak (do bardziej złożonego) na A5/1. Opisano nowe ataki na protokoły sieciowe, które wykorzystują A5/1, A5/3, czy nawet GPRS. Ataki te opierają się na błędach w bezpieczeństwie protokołów GSM i działają zawsze, gdy tylko telefon komórkowy obsługuje A5/2. Podkreślono, że są to ataki na protokoły i mogą być stosowane zawsze, gdy telefon komórkowy używa słabego szyfru, zadziałają także z zastosowaniem kryptoanalizy A5/1. W przeciwieństwie do wcześniejszych ataków na GSM, które wymagały nierealnych ilości informacji, takich jak długi znany strumień tekstu jawnego, te ataki są bardzo praktyczne i nie wymagają żadnej wiedzy o zawartości rozmowy. Ataki te pozwalają atakującym na przechwycenie rozmowy i rozszyfrowanie jej w czasie rzeczywistym lub kiedykolwiek później. Pokazano także ataki aktywne takie jak: przechwytywanie rozmowy, zmianę danych wiadomości i kradzież wywołania (rozmowa na koszt innego użytkownika).

Referat jest fragmentem pracy pt. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication E. Barkana, E. Bihama i N. Kellera opublikowanym na CRYPTO 2003.

Plan referatu:

  1. Wstęp
  2. Opis A5/2 i bezpieczeństwo GSM
    1. Bezpieczeństwo GSM: A3/A8 i GPRS
  3. Atak ze znanym tekstem jawnym na A5/2
    1. Optymalizacja ataku ze znanym tekstem jawnym na A5/2
  4. Błyskawiczny atak z samym szyfrogramem na A5/2
  5. Przełożenie ataków na wszystkie sieci GSM
  6. Możliwe scenariusze ataków
    1. Podsłuch rozmowy
    2. Przechwycenie rozmowy
    3. Zamiana danych wiadomości (sms)
    4. Kradzież rozmowy - dynamiczne klonowanie
  7. Podsumowanie


Bartosz Żółtak

Zaprezentowana zostanie odkryta przez Bartosza Żółtaka i zaprezentowana na międzynarodowej konferencji FSE'04 w Delhi, Indie, funkcja jednokierunkowa VMPC (Variably Modified Permutation Composition). Jest to najprawdopodobniej najprostsza znana funkcja jednokierunkowa. Podstawowy wariant funkcji wykorzystuje trzy elementarne operacje na permutacjach, podczas gdy proces odwracania tego przekształcenia wymaga średnio ok. 2260operacji. Zaprezentowany zostanie najbardziej efektywny znany autorowi algorytm odwracania funkcji VMPC.

Druga część referatu poświęcona będzie praktycznemu wykorzystaniu funkcji VMPC do budowy bardzo prostego, szybkiego i - zgodnie z dotychczasowymi analizami - w pełni bezpiecznego szyfru strumieniowego, wraz z algorytmem zarządzania kluczem i wektorem inicjującym. Omówione zostaną aspekty implementacji i bezpieczeństwa algorytmu, ze szczególnym naciskiem na szereg przewag w bezpieczeństwie VMPC nad popularnym szyfrem strumieniowym RC4.

Na zakończenie przedstawiona zostanie koncepcja - Tail-MAC - bardzo prostego algorytmu obliczania sum kontrolnych (tzw. Message Authentication Codes) dla szyfrów strumieniowych - na przykładzie systemu opartego na algorytmie VMPC.


Bartosz Źrałek

Omawiam metodę implikującą efektywny algorytm faktoryzacji liczb Carmichaela. Uogólnia ona metodę Pollarda i w szczególności implikuje test Millera Rabina. Opisuję uproszczoną wersję tego ostatniego - test Lehmanna - oraz test Fermata, deterministyczny na podzbiorze N dużej gęstości.


Sławomir Barabasz

Od 1979 r., kiedy Adi Shamir i niezależnie George Blakley wprowadzili koncepcje podziału tajemnicy, powstało mnóstwo pomysłów praktycznego wykorzystania i realizacji tego typu schematów. W swoim referacie przedstawię pomysły, które towarzyszyły rozwojowi Progowych Schematów Podpisu oraz kilka ich współczesnych implementacji.


Ewa Rozwenc

Funkcje bent to funkcje maksymalnie nieliniowe względem wielu kryteriów nieliniowosci, jednak nie spełniające wszystkich kryteriów niezbędnych, aby znalazły zastosowanie do konstrukcji systemów kryptograficznych. Referat zawierać będzie omówienie podstawowych własności funkcji bent, ze szczególnym uwzględnieniem ich przydatności do stosowania w szyfrach blokowych typu DES. Przedstawione będą również przykłady konstrukcji omawianych funkcji.


Aneta Zwierko

Tematem prezentacji będzie system mikropłatności MINX: Micropayments with Secure Network Exchange. System ten posiada wszystkie własności wymagane od mikropłatności: operacje są efektywne obliczeniowo, a zapewniany poziom bezpieczeństwa stosunkowo wysoki. Poza tym ma on unikatowe własności karty pre-paid oraz zapewnia użytkownikowi pewną anonimowość. Umożliwia on również utajnienie wymiany danych między operatorem a użytkownikiem. Inną zaletą jest brak jakiejkolwiek zaufanej trzeciej strony i systemu klucza publicznego. Przed omówieniem systemu przedstawione zostaną ogólnie płatności elektroniczne i systemy mikropłatności.


Kamil Kulesza (IPPT)

Addressing new challenges by building security protocols around graphs
We discuss the use of graphs as basic objects in security/cryptographic protocols. While having all the functionality of their number based counterparts; such protocols can have extended capabilities, especially useful in the field of verification and analysis. The scalability and transitivity for graph related properties allow for addressing protocols of increasing complexity. These features also cater for new challenges in the future, which will be briefly discussed. Some examples of graph based protocols will be presented.


mgr Kamil Kulesza z Instytutu Podstawowych Problemów Techniki

Na początku przewidywany jest krótki wstęp o grafach i ich kolorowaniu.
Następnie zaprezentowane zostanie twierdzenie określające górne ograniczenie liczby grafów o zadanej ilości wierzchołków, takich, że mogą zostać pokolorowane n kolorami. Rezultat ten jest następnie wykorzystywany do konstrukcji metody kodowania liczb z wykorzystaniem kolorowania grafów. Efektywność proponowanej metody rośnie wraz z długością sprawdzanych liczb i prawdopodobieństwem wystąpienia błędów.


dr Mariusz Skałba

W referacie będzie udowodniona pewna hipoteza dotycząca liczb pseudopierwszych. Pozwoli to łatwo rozkładać na czynniki pewne liczby pseudopierwsze Lucasa. Wykład ten jest głosem w dyskusji nad poprzednim referatem.


prof. dr hab. Jerzy Browkin

Wiele jest twierdzeń następującej postaci:

Jeżeli liczba naturalna n jest pierwsza, to spełnia warunek W.

Liczbę naturalną złożoną n nazywamy pseudopierwszą w sensie W, jeżeli spełnia warunek W.

Gdyby warunek W był łatwy do sprawdzenia i liczb pseudopierwszych w sensie W było "mało", to mielibyśmy dogodny sposób sprawdzania, czy dana liczba naturalna n jest pierwsza. Sprawdzalibyśmy po prostu, czy spełnia warunek W i czy należy do krótkiej listy liczb pseudopierwszych w sensie W.

W referacie zamierzam omówić pewien nowy rodzaj liczb pseudopierwszych określonych przez J. Granthama w 2000 r. zwanych liczbami pseudopierwszymi Frobeniusa.


mgr Maciej Kwiatkowski z UW

W trakcie referatu chciałbym przedstawić nowy protokół mikropłatności czyli dokonywania transakcji elektronicznymi pieniędzmi o wartości nie przekraczającej 1 EURO. Będzie on zapewniał także anonimowość, jaką dają pieniądze nieelektroniczne, mimo minimalnego użycia silnej kryptografii (tzn. kryptografii klucza publicznego). Proponowany system jest, jak większość protokołów mikropłatności, systemem off-line, co w połączeniu z jego kredytowym charakterem wymusza kontrolę nad wydawaniem tych samych elektronicznych banknotów w kilku miejscach (ang. overspending). Umożliwia to pewna własność protokołu uwierzytelniania Schnorra, którego zmodyfikowaną wersję zastosowałem także do tworzenia i weryfikacji podpisów cyfrowych. Bezpieczeństwo protokołu opiera się między innymi na częściowo ślepych podpisach, umożliwiających tworzenie integralnych podpisów cyfrowych zawierających jednocześnie dane podpisywane "na ślepo" (nieznane autorowi podpisu) i dane jawne, z góry ustalone przez autora podpisu i osobę go zadającą. W miarę możliwosci czasowych postaram się opisać jeden z takich protokołów częściowo ślepych podpisów cyfrowych oparty na protokole Nyberga-Rueppela.


mgr inż. Tomasz Kijko z Zakładu Kryptologii IMiBO WC WAT

W referacie przedstawione zostaną podstawowe kryteria oceny funkcji boolowskich pod kątem wykorzystania ich w systemach kryptograficznych. Przedstawione zostaną metody wyznaczania nieliniowości, rzędu algebraicznego i odporności korelacyjnej funkcji boolowskiej. Pokazany zostanie sposób wykorzystania algorytmów genetycznych do wyszukiwania funkcji o odpowiedniej nieliniowości.


mgr inż. Krzysztof Mańk z IMiBO WC Wojskowej Akademii Technicznej

Kolektywne generowanie klucza sesyjnego przez grupę użytkowników jest uogólnieniem idei algorytmu Diffie-Hellmana wymiany klucza między dwoma użytkownikami nie dysponującymi tajnym kanałem łączności. Powstanie algorytmów pozwalających grupie wypracować wspólny, tajny klucz zostało wymuszone rozwojem wszelkiego rodzaju systemów konferencyjnych. Przyjmuje się, że tak wygenerowany klucz powinien być w równym stopniu wypadkową pewnych tajnych wartości wniesionych do algorytmu przez wszystkich uczestników. Obiektem naszego zainteresowania będzie potencjalna słabość niektórych z tych algorytmów, polegająca na możliwości wpływania przez część użytkowników na ostateczną wartość klucza w większym zakresie, niż to winno mieć miejsce.

Plan referatu


mgr Michał Misztal z Zakładu Kryptologii IM i BO WC Wojskowej Akademii Technicznej

Szyfr blokowy Q to nowy algorytm zgłoszony w 2000 r. do projektu NESSIE, oparty na szyfrach Rijndael i Serpent. W referacie przedstawiony zostanie krótki opis algorytmu i wyniki kryptoanalizy autora. Zaproponowano połączenie wielu charakterystyk różnicowych jako różniczek (differentials), co pozwala na skonstruowanie ataku na pełny algorytm, lepszego od pełnego przeszukiwania. Przedstawiony zostanie opis tego ataku i jego wyniki. Praca ta, której współautorami są E. Biham, V. Furman i  V. Rijmen, była zaprezentowana na FSE 2001 w Jokohamie.


prof. dr hab. Jerzy Browkin (według D.R. Stinsona, Math. Comp. styczeń 2002)

Stinson podaje algorytmy dla wyznaczenia takiego logarytmu dyskretnego, jak w tytule, i znajduje oszacowania ich (średniej) złożoności obliczeniowej. Zamierzam omówić też związane z tym problemy kombinatoryczne.


prof. dr Boris Ryabko z Uniwersytetu w Nowosybirsku

It is well known in cryptography that it is easy to construct an unbreakable secret-key cipher system if a plaintext source generates letters which are independent and equiprobable even if the length of a key sequence is much less than the length of the message. In this paper, we suggest a new secret-key cipher system in which a message generated is transformed into two parts in such a way that the biggest part consists of independent and equiprobable bits and only this part is encrypted. The complexity of the method is exponentially less than that for other known methods.


mgr Rafał Nessel

W trakcie seminarium zamierzam przedstawić stosunkowo nowy kryptosystem NTRU (1996, J. Hoffstein, J. Pipher, J.H. Silverman). W szczególności omówię wykorzystywane struktury algebraiczne, podam definicje kryptosystemu oraz podstawy jego bezpieczeństwa. Ponadto przedstawie kilka atakow na ten kryptosystem:


prof. dr hab. Marek Kuś z Centrum Fizyki Teoretycznej PAN
Kryptografia kwantowa zajmuje sie problemem bezpiecznej dystrybucji klucza,
tzn. proponuje sposob przesylania informacji w taki sosob aby po zakonczeniu
transmisji nadawca i odbiorca dysponowali ta sama informacja a jednoczesnie
mieli pewnosc, ze informacja ta pozostaje nieznana innym. W celu zapewnienia
bez jej bezpowrotnego zniszczczenia.

W czasie wykladu zamierzam przedstawic;
1. najwazniejsze protokoly kryptografii kwantowej tzn.
  a. protokol Benneta-Brassarda (BB84) wykorzystujacy dwie rozne reprezentacje
     ukladu kwantowego o dwu stanach ("dwa alfabety"),
  b. protokol Benneta (B92), rowniez wykorzystujacy kwantowe uklady dwustanowe,
     jednak przy uzyciu jednego alfabetu,
  c. protokol Ekerta wykorzystujacy lamanie nierownosci tzw. Bella przez uklady
     kwantowe
2. najwazniejsze i najnowsze realizacje doswiadczalne kwantowych dystrybucji
     klucza - osiagniecia i trudnosci.