Lade Inhalt...

Mersenne- und Fermat-Primzahlen oder auf der Suche nach großen Primzahlen

Bachelorarbeit 2010 33 Seiten

Mathematik - Algebra

Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Biographien
2.1 Pierre de Format
2.2 Marin Morsenno

3 Kryptographie
3.1 Geschichtlicher Hintergrund
3.2 Theorie der Kryptographie
3.3 RSA mit Mersonne-Primzahlon

4 Primzahlen
4.1 Die Bedeutung von Primzahlen in der Kryptographie
4.2 Voraussetzungen zu den Beweisen
4.3 Mersenne'sehe Primzahlen
Satz 4.3.1
Satz 4.3.2
Satz 4.3.3
Zusammenfassung
4.4 Fermat'sehe Primzahlen
Satz 4.4.1
Satz 4.4.2
Satz 4.4.3
Zusammenfassung

5 Schlussteil und weiterführende Gedanken

6 Literaturverzeichnis
6.1 Buch
6.2 Zeitsehriftenartikel
6.3 Sammelwerk
6.4 Internet
6.5 Bildnachweis

Anhang

1 Einleitung

Wie findet man Primzahlen? Schon in der späteren Schulzeit hat mich diese Frage interessiert, da es anscheinend kein effizientes Verfahren hierzu gibt. Es scheint stattdessen sogar, als sei die Verteilung von Primzahlen zufällig auf dem Zahlenstrahl der natürlichen Zahlen verstreut, wobei diese bei zunehmender Größe rarer werden.

Einige Verfahren existieren jedoch, mit deren Hilfe sich Primzahlen aufspüren lassen. Zwar gibt es bis zur bis heute größten gefundenen Primzahl vermutlich noch weitere, kleinere, die sich noch nicht offenbart haben und zu denen es bislang keinen effizienten mathematischen Zugang zum Aufspüren gibt, doch können einige auf schnellem Wege dennoch gefunden werden.

In dieser Arbeit sollen vorrangig diese effizienten Methoden beschrieben werden, mit denen sich gezielt große Primzahlen von besonderer Bauart finden lassen.

Tieferen Einblick hierzu bekam ich durch das fachwissenschafiliche Seminar zur Kryptographie, in dem ich mich mit zwei solcher Verfahren intensiv beschäftigt habe, Neben FERMAT entwickelte insbesondere MERSENNE seinerzeit einen einfachen Weg, große Primzahlen zu bestimmen, Kurzbiographien zu den beiden Mathematikern sind dem folgenden Kapitel zu entnehmen.

Anschließend werde ich mich auf diese beiden Verfahren beschränken und daher auf die sogenannten Merse.nne- und Fe.rmat-Zahle.n eingehen, welche unter bestimmten Voraussetzungen Primzahlen - wenn auch nicht sämtliche - liefern.

Entsprechende Sätze und Beweise finden sich in den Kapiteln 4,3 und 4,4 wieder, wobei sich ersteres speziell mit MERSENNE-Zahlen, letzteres mit den FERMAT-Zahlen befasst. Um die Beweisführung verständlicher zu gestalten, habe ich am Ende dieser Arbeit einen ausführlichen Anhang erstellt. Dabei entscheide ich mich bewusst dagegen, die im Anhang befindlichen Zwischenschritte direkt in die Beweise zu integrieren, um einen angenehmeren Lesefluss zu ermöglichen. Der Leser kann nun selbst entscheiden, ob er - falls Bedarf besteht - auf den Anhang zurückgreifen oder sich bei ausreichendem Verständnis lediglich auf die Beweise an sich beschränken möchten.

Des weiteren wird erklärt, weshalb große Primzahlen in der modernen Kryptographie eine solch wichtige Rolle spielen.

Da bis vor relativ kurzer Zeit Primzahlen in der Praxis kaum Anwendung fanden und hauptsächlich erst in der modernen Kryptographie Verwendung finden, gehe ich in Kapitel 3 auf die essentielle Bedeutung von Primzahlen in der Kryptographie ein.

Weshalb ausgerechnet MERSENNE- und FERMAT-Primzahlen für die praktische Anwendung in der Regel allerdings ungeeignet sind, wird darin anhand eines Beispiels zum

RSA-Verfahren (s, Kap, 3,3) ebenfalls erläutert, Ausnahmen, bei denen MERSENNE-Primzahlen doch eine Verwendung finden, bieten beispielsweise elliptische Kurven, Deren zugrundeliegende Mathematik ist aber derart komplex, dass sie selbst in einem Klassiker zur Kryptographie von Bruce Schneier nicht näher erläutert wird1 und daher den Rahmen dieser Arbeit bei weitem überschreiten würde.

In Kapitel 3 gebe ich zudem sowohl einen geschichtlichen Hintergrund zur Entstehung der Kryptographie als auch eine Darlegung des Ablaufes eines Kryptosystem,

Die Arbeit beende ich in Kapitel 5 mit einem Fazit, Dort erläutere ich noch einmal kurz, wie ich bei den Beweisen der FERMAT- und MERSENNE-Primzahlen vorgegangen bin. Außerdem gebe ich einen kleinen Ausblick auf die Zukunft der Kryptographie und erläutere sowohl Vor- als auch Nachteile von geheimer Kommunikation,

2 Biographien

2.1 Pierre de Fermat

Pierre de fermat wurde 1607 oder 16082 als Sohn von Dominique de Fermat, dem zweiten Bürgermeister von Geau-mont de Lomagne an der Gimon in Bordeaux geboren. Seine Mutter Ciaire de Long war Tochter einer Juristenfamilie,3 Schon während der Schulzeit erwarb fermat umfassende Sprachkenntnisse in Griechisch, Spanisch und Italienisch, sodass es ihm möglich war, handgeschriebene Originale zu lesen und Fehler gar zu verbessern,4

Fermat studierte zunächst in Toulouse und Bordeaux,0 Letztere war jene Stadt, in welcher er seine „ersten großen mathematischen Entdeckungen"5 machte,' Anschließend absolvierte er ein Jurastudium in Orleans und wurde Anwalt am Obersten Gerichtshof in Toulouse,6

Im Laufe seines Lebens wurde er in Bezug auf sein mathematisches Streben vorwiegend beeinflusst durch die mathematischen Schriften der Griechen Pappos (um 320 n, Chr.)7 und Archimedes (287 - 212 v, Chr.)8 und Korrespondenzen mit dem aus Frankreich stammenden Viete (1540 - 1603)9 , Des weiteren verbesserte und bereicherte er die Arith-metica des ebenfalls aus Griechenland stammenden Diophant (um 250 n, Chr.)10 und gilt als Begründer der Zahlentheorie11 , Er verfasste außerdem wichtige Werke in der Differentialrechnung12 , der analytischen Geometrie10 und weiteren mathematischen Gebieten,

Eine seiner bekanntesten und spektakulärsten Aussagen ist der Große Satz von Fermat. Hierzu schreibt fermat auf Latein auf den Rand seiner Arithmetiea: „Ich habe einen wahrhaft wunderbaren Beweis gefunden, aber dieser Rand ist zu schmal, ihn zu fassen,"13 ,14 ' Der Große Satz von Fermat besagt, dass es keine ganzzahligen Lösungen für ax + bx = cx mit x E N, x > 2 gibt,15 Erst 1995, nachdem Jahrhunderte kein Mathematiker dazu in der Lage war, konnte Andrew Wiles den 130 Seiten umfassenden Beweis führen,16 Man vermutet daher, FERMAT hatte irrtümlicherweise angenommen, einen Beweis gefunden zu haben, wahrscheinlich mithilfe der von ihm entwickelten de.sce.nte infinie., bei der ähnlich der vollständigen Induktion vorgegangen wird,17

Auch der Kleine Satz von Fermat gilt in der Zahlentheorie als wesentlich: ap-1 = 1 mod p, p E P18 und findet heutzutage in der Kryptographie regelmäßige Anwendung, wenn auch in etwas abgewandelter Form,19

Zudem gilt er als Vater der Wahrscheinlichkeitsrechnung, deren Geburtsstunde auf einen Briefwechsel mit dem Mathematiker Chevalier de Mere über die gerechte Aufteilung des Gewinnes bei einem abgebrochen Glücksspiel zurückzuführen ist,20

Erst nach seinem Tod 1665 im Alter von 57 Jahren wurde erkannt, welch bedeutender Mathematiker Pierre de FERMAT gewesen war. Dies belegen seine zahlreichen, meist unvollständigen Schriften und umfangreichen Korrespondenzen mit Mathematikern aus ganz Europa,21

2.2 Marin Mersenne

Marin MERSENNE lebte von 1588 bis 1648,22 Geboren wurde er in Main nahe Dijon und starb in Paris, wo er als Franziskanerpater tätig war,23 Bis heute sind seine ausgedehnten Korrespondenzen fast vollständig erhalten und von großer historischer Bedeutung,24 '

Von Beruf war er sowohl Theologe als auch Philosoph, ebenso wie Mathematiker und Musikwissenschaftler,25 Sein größtes Ziel war es jedoch, die Existenz Gottes nachzuwei-

'29

sen,

MERSENNE kommunizierte schriftlich mit mathematischen Größen wie Descartes und Galilei, welche er auch gegen theologische Angriffe seitens der Kirche verteidigte. Er spielte daher eine führende Rolle in der Weitergabe mathematischen Wissens in Europa, beispielsweise durch seine teilweisen Übersetzungen von Galileis Dialogo und Discorsi ins Französische,26 Die Korrespondenz mit FERMAT wurde von dessen Sohn recht bald veröffentlicht wurde,27

MERSENNE verbrachte mehrere Jahre mit Reisen durch Mitteleuropa und setzte sich 1640 in Italien zur Ruhe, um sich kurz vor seinem Tod ein letztes Mal nach Paris zu begeben,28

3 Kryptographie

3.1 Geschichtlicher Hintergrund

Ursprünge der Kryptographie finden sieh schon im fünften Jahrhundert vor Christus im Krieg zwischen Griechenland und Persien, in dem die Griechen unter Herodot der Eroberung durch Xerxes aufgrund einfacher, seinezeit aber effektiver Methoden zur Verschlüsselung von Nachrichten entgehen konnten,29 Berühmter ist hingegen sicherlich die nach Julius Caesar benannte Caesar-Chiffre, bei der jeder Buchstabe des Alphabets um drei Buchstaben verschoben wird:

Abbildung in dieser Leseprobe nicht enthalten

Auch hier nutzte Caesar seine Chiffriermethode vorrangig zur militärischen Sicherheit, Die Caesar-Chiffre ist ein Spezialfall der sogenannten Substitutionschiffre, Hier werden nach einem Schema Buchstaben um jeweils eine bestimmte Position verschoben.

Wurde bis dato per Hand verschlüsselt, erfand im 15, Jahrhundert der italienische Architekt Leon Alberti die Chiffrierscheibe30 , mit deren Hilfe sich die Anwendung der Substitutionschiffre stark vereinfachen ließ. Mit der Weiterentwicklung von Chiffriermaschinen kam es schließlich zu einer der bekanntesten kryptographischen Erfindungen: der Enigma, Sie diente ebenfalls vorrangig als militärisches Hilfsmittel im zweiten Weltkrieg, Während bislang ein steter Kampf zwischen Kryptogra-

phen und Krvptoanalvtikern tobte, errangen erstere mit der r<l. ,

1 -1 ° Abbildung 3: Lnifmerscneibe

Entwicklung des sogenannten Public-Key-Verfahren einen (http://upload.wikimcdia.org) bis heute bestehenden Vorteil,30 Den ersten Durchbruch in

dieser Hinsicht schafften Whitfield Diffie und Martin Hellman mit dem nach ihnen benannten Diffie-Hellman-Sehliisseltauseh (1976),31 Zwei Partner entscheiden sich hierbei gemeinsam für einen öffentlichen Schlüssel, der jedem Außenstehenden bekannt sein darf, und jeweils einem privaten, den nicht einmal der Partner kennt. Somit ist eine sichere und geheime Kommunikation zwischen diesen Partnern möglich. Einen Nachteil hat dieses Verfahren allerdings: es ist recht langwierig,

Heutzutage ist es insbesondere das RSA-Verfahren, benannt nach seinen Entwicklern Rivest, Shamir und Adleman, das seit 19783 ' zur sicheren und raschen Übermittlung geheimer Botschaften beiträgt (s, Kap, 3,3),

Xeben militärischen Zwecken kommt Kryptographie mittlerweile ebenso in der Wirtschaft sowie in der modernen Archäologie zur Anwendung, Dort dient die Kryptoanalyse den Forschern vor allem zum Entziffern alter Schrift, Eine der größten Leistungen bildete hierbei die Entschlüsselung von Linear B, einer in Kreta während der Bronzezeit entstandenen Schrift, 53 Jahre dauerte es von der Entdeckung bis zur offiziellen vollständigen Entzifferung im Jahr 1953,32

3.2 Theorie der Kryptographie

Die heutige Kryptographie beschäftigt sich mit sogenannten Kryptosystemen, Diese bestehen aus dem mit m oder p bezeichnetem Klartext (engl, message/plaintext) und dem Geheimtext c (engl. Chiffretext), Die Verschlüsselungsfunktion E (engl, encrvption) verschlüsselt den Klartext in den zu versendenden Geheimtext: E(m) = c. Umgekehrt entschlüsselt D (engl, decrvption) den erhaltenen Chiffretext wieder zum Klartext: D(c) = m. Da der Geheimtext eindeutig in den ursprünglichen Klartext umgewandelt werden soll, muss gelten D (E(m)) = m. Ver- und entschlüsselt wird mithilfe eines Schlüssels k (engl, kev) aus dem Schlüsselraum, Dadurch ergibt sich für die Verschlüsselung Ek(m) = c und Dk(c) = m für die Entschlüsselung,33

Ziel der Kryptographie ist es, eine geheime Kommunikation zwischen Sender und Empfänger zu ermöglichen, die von Außenstehenden nicht abgehört werden soll. Der Sender wird dabei in der Regel mit A für Alice, der Empfänger mit B für Bob bezeichnet. Der sogenannte Lauscher, also die Person, die versucht, durch Knacken der Verschlüsselung in Besitz des Klartextes zu gelangen, wird Eve benannt (nach dem engl, für eavesdropper). In der Kryptographie wird zudem zwischen symmetrischen und asymmetrischen Schlüsseln unterschieden. Bei der symmetrischen Kryptographie ist der Verschlüsselungsschlüssel der gleiche wie jener zur Entschlüsselung, Wird asymmetrisch verschlüsselt, ist dieser Schlüssel keine Hilfe bei der Entschlüsselung und kann daher öffentlich bekannt gegeben werden. In vielen asymmetrischen Kryptosystemen ist die Bekanntgabe des Verschlüsselungsschlüssels Voraussetzung für eine erfolgreiche Kommunikation, Man spricht daher auch von Public-Key-Verfahren,

3.3 RSA mit Mersenne-Primzahlen

Das RSA-Verfahren ist benannt nach seinen Entwicklern Rivest, Shamir, Adleman3435 und das heute meist benutzte Public-Key-Verfahren, Überhaupt gilt es historisch als das erste Kryptosystem mit öffentlichem Schlüssel,36 Der Vorgang ist folgendermaßen:

a) Zunächst wählt Bob, der eine Nachricht empfangen will, zwei unterschiedliche Primzahlen p und q und bildet daraus das Produkt n = p • q. Des weiteren wählt er ein e E N mit ggT (e, p(n)) = 1, wobei p(n) = (p — l)(q — 1). Außerdem berechnet er d = e-1 mod p(n), Den öffentlichen Schlüssel (n, e) sendet er an Alice, den privaten Schlüssel (p(n),d) hält er geheim,

b) Alice schreibt eine Nachricht m und chiffriert sie als c = me mod n, welche an Bob gesandt wird,

c) Bob entschlüsselt c, indem er m = cd mod n berechnet.

Die Sicherheit des RSA-Verfahrens ist begründet durch das ineffiziente Faktorisieren np q bekannt, könnte sie schnell p(n) und somit d berechnen und anschließend alle an Bob gesendeten Nachrichten entschlüsseln,

n

der Schlüssel geknackt werden kann, wird im folgenden Beispiel veranschaulicht. Es wird dabei auf das folgende Kapitel vorgegriffen, in dem erläutert wird, welche Primzahlen von der MERSENNE-Bauart sind. Angenommen, der öffentliche Schlüssel von Bob lautet n = 203 und e =11 und Eve

n

Alice schickt c = 125 mod 203 (mit m = 6 ist c = me = 611 = 125 mod 203, was Eve allerdings nicht bekannt ist) an Bob, welcher mithilfe des privaten Schlüssels durch m = cd mod n wiederum auf m = 6 kommt,

n

besteht, schnell den geheimen Schlüssel berechnen. Da in diesem Beispiel relativ kleine Primzahlen genommen werden, ist dies durch versuchsweise Division37 möglich, da es relativ wenig MERSENNE-Primzahlen gibt, wobei diese in unserem Beispiel zudem kleiner.

[...]


1 iVgl. Schneid' (2006), S. 548

2 Vgl. Strick (2009), S. 36

3 Vgl. Hofmann, Band I (1990), S. 402

4 Vgl. ebd.

5 Hofmann, Band I (1990), S. 402

6 Vgl. Strick (2009), S. 36

7 »Vgl. Hofmann (1963), S. 277

8 Vgl. Kordos (1999), S. 281

9 Vgl. Hofmann (1963), S. 146

10 Vgl. ebd., S. 207

11 Vgl. Kaiser: Nöbauor (1998), S. 62

12 "Vgl. Strick (2009), S. 36

13 "Strick (2009). S. 37

14 "Originalausgabe s. Kap. 7 Anhang, 1.

15 Vgl. Kaiser: Nöbauor (1998), S. 43

16 1B Vgl. Sirigh (1998), S . 311

17 Vgl. Strick (2009), S. 37

18 S. Kap. 4-2 Voraussetzungen zu den Beweisen, 1.

19 S. Kap. Jt.l Die Bedeutung von Primzahlen in der Kryptographie

20 Vgl. Strick (2009), S. 37

21 Vgl. ebd.

22 Vgl. Hofmann (1963), S. 223

23 Vgl. Kordos (1999), S. 137

24 "Vgl. ebd.

25 Vgl. http://d-nb.info

26 Vgl. http://www.mathematik.ch

27 Vgl. Kordos (1999), S. 144

28 Vgl. http://www.bantz.de

29 Vgl. Singh (2000), S. 18

30 Vgl. ebd., S. 156

31 Vgl. ebd., S. 323

32 Vgl. Sirigh (2000), S. 266ff.

33 Vgl. Schneier (2006), S. lf.

34 Vgl. für den Vorgang des RSA-Verfahrens: Scheid: Frommer (2007), S. 207

35 Vgl. Bauer (1997), S. 186

36 Vgl. Scheid: Frommer (2007), S. 207

37 Vgl. Schneier (2006), S. 300

Details

Seiten
33
Jahr
2010
ISBN (eBook)
9783656177357
ISBN (Buch)
9783656177555
Dateigröße
1.9 MB
Sprache
Deutsch
Katalognummer
v191899
Institution / Hochschule
Universität Hildesheim (Stiftung)
Note
Schlagworte
Bachelor Bachelor-Arbeit Mersenne Fermat Mersenne-Primzahlen Fermat-Primzahlen Fermatsche Primzahlen

Autor

Zurück

Titel: Mersenne- und Fermat-Primzahlen oder auf der Suche nach großen Primzahlen