Mathematische Puzzles - Weblearn

Transcrição

Hochschule Bremen
Fakultät E-Technik & Informatik
Mathematische Puzzles
Prof. Dr. Th. Risse
Anregendes, Bereicherndes, Cooles, Einschlägiges, . . .
Informatives, . . .
Kurzweiliges, Lehrreiches, Merkwürdiges, . . .
Praktisches, . . .
Spielerisches, . . .
Unterhaltsames, . . .
Zuträgliches,
ein kleiner Beitrag zur mathematischen (Allgemein-) Bildung!
c 2002–2014
Letzte Änderung: 8. August 2014
risse(at)hs-bremen.de
Version 0.5
Inhaltsverzeichnis
0. Einbettung
1. Rätsel [7]
• Abmessen mit zwei Gefäßen • Rennen • Volkszählung bzw.
Volkszählungsboykott • Zick-Zack zwischen Zügen • Hinund Rück-Reise • Magische Quadrate • Auffälliger Text
• Über Geld spricht man nicht • korruptes Postsystem
• Gleichberechtigung • Zwei- und Mehr-Augen
2. Mehr Rätsel [11]
• Streichhölzer • Umfüllen • Analytische Rätsel I • Analytische Rätsel II • Analytische Rätsel III • Analytische Rätsel
IV • Analytische Rätsel V • Brückenquerung • Synthetische
Rätsel I • Synthetische Rätsel II • Synthetische Rätsel III
• Synthetische Rätsel IV • Dialektisches Rätsel • Rätsel, 588
• Rätsel, 622 • Labyrinth, 652 • Rätsel, 680 • Rätsel, 708
• Rätsel, 734 • Rätsel, 750 • Rätsel, 772
3. Prim-Zahlen
Inhaltsverzeichnis (Forts.)
3
• Fermat-Zahlen • Euler-Zahlen • Mersenne-Zahlen
4. Rechnen mit Divisionsresten
• Entscheidend ist, was übrig bleibt • mit Resten rechnen
• geschickt mit Resten rechnen • Euklid & der kleine Fermat
• Fermat, Euler und mehr • Chinesisches • Galois-Körper
GF(p) • Galois-Körper GF(pn )
5. Kryptographie
• Caesar und Kohorten • Caesar generell • Vigenère und
Konsorten • tarnen, tauschen und ... • DES • öffentliche
Schlüssel? • RSA • AES • Elliptische Kurven über R • Elliptische Kurven über GF(p) • Elliptische Kurven über GF(2m )
• Elliptic Curve Cryptography, ECC
6. Kompression
• Ausnutzen relativer Häufigkeiten • Wörterbücher nutzen
7. Wahrscheinlichkeit & Intuition
• Karten & Ziegen • Algorithmen erzeugen Zufall? • Was ist
zufällig am Zufall?
8. Quellen und links
Lösungen zu Problemen
4
0. Einbettung
Zur Einstimmung finden Sie einige mathematische Rätsel. Ernsthafter
und weniger spielerisch gemeint ist die Präsentation grundlegender
Verfahren der Kryptographie, Codierung, Wahrscheinlichkeit etc. zum
Ausprobieren. Viele im Dokument eingebettete Algorithmen erlauben,
diese Verfahren selbst zu untersuchen.
Weitere interaktive Dokumente sind z.B.
www.weblearn.hs-bremen.de/risse/MAI/docs/numerik.pdf oder
www.weblearn.hs-bremen.de/risse/MAI/docs/heath.pdf.
Die Funktionalität von pdf-Dokumenten erlaubt Ihnen,
bequem sich die Sie interessierenden Problem-Felder oder EinzelProbleme • auszusuchen und Algorithmen auszuführen,
leicht von Problemstellung zur Lösung und zurück zu blättern,
einfach auch die zahlreichen links auf Informationen auf unserem
webDAV server oder im WWW zu besuchen.
5
1. Rätsel [7]
• Abmessen mit zwei Gefäßen
Problem 1. Zur Verfügung stehen zwei Gefäße mit p ` und q ` Fassungsvermögen und beliebig viel Wasser.
Können bestimmte Wassermengen m abgemessen werden?
(a) p = 5, q = 3, m = 4
(b) p = 5, q = 3, m = 1
(c) p = 4, q = 9, m = 1, 2, . . . , 13
(d) p = 6, q = 3, m = 4
• Rennen
Problem 2.
(a) Beim Gipfelsturm auf einen 3000er schafft Sisyphos pro Tag 300
Höhenmeter, rutscht aber während jeder Nacht wieder um 200
Höhenmeter zurück.
Am wievielten Tag erreicht Sisyphos den Gipfel?
Abschnitt 1: Rätsel [7]
6
(b) Bei einem 100m Rennen schlägt der Erste A den Zweiten B um
10m. Der Zweite B schlägt den Dritten C um 10m.
Um wieviele Meter schlägt der Erste A den Dritten C ?
• Volkszählung bzw. Volkszählungsboykott
Problem 3.
(a) Bei einer Volkszählung entspinnt sich folgender Dialog:
Zähler:
Anzahl der Kinder?
Merkmalsträger: drei!
Zähler:
ganzzahliges Alter der Kinder?
Merkmalsträger: Das Produkt der Jahre ist 36.
Zähler:
Diese Auskunft reicht mir nicht!
Merkmalsträger: Die Summe der Jahre stimmt mit der
Hausnummer unseres Nachbarn überein.
(Der Zähler ermittelt die Hausnummer.)
Zähler:
Das reicht mir immer noch nicht!
Merkmalsträger: Unser ältestes Kind spielt Klavier.
Wie alt sind die drei Kinder?
7
• Zick-Zack zwischen Zügen
Problem 4.
(a) Zwei Züge starten auf derselben Strecke 100km entfernt und fahren mit 50km/h aufeinander zu. Ein Fliege fliegt mit 75km/h zwischen diesen beiden Zügen hin und her.
Wieviele Kilometer hat die Fliege bis zur unausweichlichen Katastrophe zurückgelegt?
• Hin- und Rück-Reise
Problem 5.
(a) Jemand macht sich mit Sonnenaufgang in A auf wandert mit beliebigen Pausen nach B, wo er bei Sonnenuntergang eintrifft. Am
nächsten Tag erfolgt die Rückreise auf demselben Weg: Aufbruch
bei Sonnenaufgang in B, beliebige Pausen, Rückkunft bei Sonnenuntergang in A.
8
Es gibt einen Punkt des Weges, den der Reisende auf Hin- und
Rückweg zu genau derselben Tageszeit passiert.
• Magische Quadrate
Problem 6.
(a) Magische Quadrate sind Anordnungen natürlicher Zahlen in quadratischen Matrizen, so daß die Summen der Elemente in jeder
Spalte, Zeile und Diagonale identisch sind.
a b c
a + b + c = s ...
a + d + g = s ...
mit
d e f
a + e + i = s ...
g h i
Es gibt bis auf Symmetrie genau ein magisches Quadrat mit den
natürliches Zahlen 1, 2, . . . , 9 angeordnet in einer 3 × 3-Matrix.
• Auffälliger Text
Problem 7.
9
(a) Study this paragraph and all things in it. What is virtually wrong
with it? Actually, nothing in it is wrong, but you must admit
that it is most unusual. Don’t zip through it quickly, but study
it scrupulously. With luck you should spot what is so particular
about it. Can you say what it is? Tax your brains and try again.
Don’t miss a word or a symbol. It isn’t all that difficult.
• Über Geld spricht man nicht
Problem 8.
(a) Ein Personalchef möchte das Durchschnittsgehalt der Mitarbeiter
einer Abteilung ohne Verstoß gegen Datenschutz usw. ermitteln,
d.h. ohne von individuellen Gehältern Kenntnis zu nehmen.
• korruptes Postsystem
Problem 9.
10
(a) In einem korrupten Postsystem wird jeder Brief geöffnet und der
Inhalt unabhängig von seinem Wert entfernt. Nur sicher verschlossene Kisten (strong box) werden zuverlässig befördert.
Wie kann Bob seiner Alice ein wertvolles Schmuckstück in einer
mit mehreren Vorhänge-Schlössern zu sichernden Kiste schicken,
wenn sich Alice und Bob über Art und Weise des Transfers (etwa
telephonisch) verständigen können?
• Gleichberechtigung
Problem 10.
(a) Alice und Bob haben eine Wochenendbeziehung. Sie wollen sich
wechselweise besuchen und durch Münzwurf herausfinden, wer am
nächsten Wochenende mit der Fahrerei anfängt.
11
• Zwei- und Mehr-Augen
Problem 11. Vom Zwei-Augen-Prinzip spricht man, wenn zwei Personen mit je einem Schlüssel oder wenn zwei Passwörter nötig sind, um
einen Tresor oder eine Datei zu öffnen. Jede Person öffnet mit ihrem
Schlüssel ihr Tresor-Schloß oder fügt ihr Teil-Passwort mit demjenigen
der anderen Person zum vollständigen Passwort zusammen.
(a) Alice, Bob und Claire verfügen über einen Tresor mit diversen
Schlössern. Sie wollen sicherstellen, daß nur mindestens zwei Personen zusammen den Tresor öffnen können.
Mit wievielen Schlössern und wievielen Schlüsseln zu jedem Schloß
ist dies zu bewerkstelligen?
(b) Jetzt wollen Alice, Bob, Claire und Denis sicherstellen, daß nur
mindestens zwei Personen zusammen den Tresor öffnen können.
Minimal wieviele Schlössern und minimal wieviele Schlüssel zu
jedem Schloß sind nötig?
(c) Nur mindestens m von insgesamt n Personen sollen zusammen
den Tresor öffnen können. Wieviele Schlösser, wieviele Schlüssel?
12
2. Mehr Rätsel [11]
• Streichhölzer
Problem 12. Es sind eine gegebene Anzahl von Streichhölzern so
umzulegen, daß eine gegebene Anzahl gleich großer Quadrate entstehen.
(a)
Man lege vier Streichhölzer so um, daß drei gleich
große Quadrate entstehen.
(b)
Man lege zwei Streichhölzer so um, daß vier gleich
(c)
Man lege drei Streichhölzer so um, daß drei gleich
(d)
Man lege drei Streichhölzer so um, daß fünf gleich
Abschnitt 2: Mehr Rätsel [11]
13
• Umfüllen
Problem 13.
(a) Wie kann man 6 Liter Wasser aus einem Fluß abfüllen, wenn nur
ein 4-Liter- und ein 9-Liter-Eimer zur Verfügung stehen?
(b) Wie kann man genau 1 Liter Wasser aus einem Behälter abmessen, wenn nur ein 3-Liter- und ein 5-Liter-Behälter zur Verfügung
stehen?
(c) Ein 8-Liter-Kanister sei voll Weins. Wie kann man genau 4 Liter abmessen, wenn nur ein 3-Liter- und ein 5-Liter-Krug zur
Verfügung stehen?
(d) Ein Faß enthalte 18 Liter Weins. Es gibt einen 2-Liter-Becher,
einen 5-Liter-Krug und einen 8-Liter Eimer. Wie kann man den
Wein so verteilen, daß sich die Hälfte im Faß, ein Drittel im Eimer
und ein Sechstel im Krug befinden?
• Analytische Rätsel I
Problem 14.
14
(a) Die Summe der Lebensalter der Mitglieder einer Familie, Vater,
Mutter und zwei Kinder, sei 124. Vater und Mutter sind zusammen dreimal so alt wie die Kinder. Die Mutter ist mehr als doppelt
so alt wie das älteste Kind. Die Differenz Alter des Vaters minus
Alter der Mutter sei neunmal so groß wie die Differenz Alter des
älteren Kindes minus Alter des jüngeren Kindes. Wie alt ist jedes
Familien-Mitglied?
(b) Emil ist 24 Jahre alt. Er ist damit doppelt so alt wie Anton war,
als Emil so alt war, wie Anton jetzt ist. Wie alt ist Anton?
(c) In einem Kaufhaus bekommt man 20% Rabatt, muß aber 15%
Umsatzsteuer zahlen. Ist es günstiger, zuerst den Rabatt abzuziehen oder zuerst den Steueraufschlag vorzunehmen?
2
1
(d)
Die L-förmige Fläche ist in vier kongruente
Teilflächen zu zerlegen.
2
1
(e) Wenn Fritz 5 Jahre jünger wäre, dann wäre er zweimal so alt wie
15
Paul war, als er 6 Jahre jünger war. Wenn Fritz 9 Jahre älter wäre,
dann wäre er dreimal so alt wie Paul, wenn Paul 4 Jahre jünger
wäre. Wie alt sind Fritz und Paul?
• Analytische Rätsel II
Problem 15.
(a)
(b)
(c)
(d)
Die Ecken des Dreieckes sind mit unbekannten
11
18 natürlichen Zahlen etikettiert. Die Kanten sind
mit der Summe der Etiketten der inzidenten
Ecken etikettiert. Wie lauten die Etiketten der
27
Ecken?
Hans ist 34 Jahre, seine Fau 30 und seine Tochter 7 Jahre alt. Vor
wievielen Jahren waren Frau und Tochter zusammen genauso alt
wie Hans?
Drei Gänse wiegen zusammen 10kg. Die zweite Gans ist um ein
Drittel schwerer als die erste. Die dritte Gans ist um ein viertel
leichter als die zweite. Wie schwer ist jede Gans?
Gibt es vier natürliche Zahlen mit Summe 79 und
16
• Die Zweite ist um 1 kleiner als das Doppelte der Ersten.
• Die Dritte ist um 1 kleiner als das Doppelte der Zweiten.
• Die Vierte ist um 1 kleiner als das Doppelte der Dritten.
(e) Ein Maultier und ein Esel schreiten mit Säcken beladen ihres
Weges. Der Esel stöhnt unter seiner Last. Darauf spricht das Maultier: Was jammerst Du? Doppelt soviel wie Du trüge ich, gäbst Du
einen Sack mir. Nähmst Du mir einen Sack ab, so trügen wir beide gleich viele Säcke. Wieviele Säcke trägt der Esel, wieviele das
Maultier?
• Analytische Rätsel III
Problem 16.
(a) Welchen Radius hat ein Kreis, der ebensoviele Zentimeter Umfang
wie Quadratzentimeter Fläche besitzt?
(b) Ein Zug fährt in 7sec am Bahnhofsvorsteher vorbei. Der Bahnsteig
ist 330m lang. Der Zug braucht 18sec von Beginn des Bahnsteiges und der Lok bis zum Ende des Bahnsteiges und des letzten
Wagens. Wie lang ist der Zug und wie schnell fährt er?
17
(c) Ein Arbeiter stellt die erste Hälfte von Werkstücken mit einer
Rate von 10 Werkstücken pro Tag und die zweite Hälfte mit 30
Werkstücken pro Tag her. Wieviele Werkstücke stellte der Arbeiter durchschittlich pro Tag her?
(d) Sind alle palindromischen vierstelligen Dezimalzahlen durch 11
teilbar?
(e) As I was going to St. Ives / I met a man with seven wives. / Each
wife had seven sacks, / Each sack had seven cats, / Each cat had
seven kids, / Kids, cats, sacks, wives, / How many were going to
St. Ives?
(f) Um welchen Bruchteil übertrifft vierviertel die Zahl dreiviertel?
• Analytische Rätsel IV
Problem 17.
(a) Wenn 5 Katzen in 5 Minuten 5 Mäuse fangen, wieviele Katzen
fangen dann 100 Mäuse in 100 Minuten?
(b) Wenn man weiß, wie man Zahlen kleiner als 6 miteinander multi-
18
pliziert, weiß man auch, wie man Zahlen zwischen 6 und 10 miteinander multipliziert: Man hält beide Hände vor sich: um etwa
7 mit 9 zu multiplizieren, senkt man 7 − 5 = 2 Finger der linken
Hand und 9 − 5 = 4 Finger der rechten Hand. Dann zählt man
die 2 + 4 = 6 gesenkten Finger und multipliziert 3 · 1 = 3 die ausgestreckten Finger der einen mit den ausgestreckten Fingern der
anderen Hand. Das Ergebnis 63 entsteht aus 6·10+3. Funktioniert
das Verfahren immer?
(c) Anderthalb Hennen legen anderthalb Eier in anderthalb Tagen.
Wieviele Eier legen sieben Hühner in sechs Tagen?
(d) Es gebe vier Sorten Kugeln A, B, C und D. Kugeln gleicher Sorte
haben gleiches Gewicht. Es ist bekannt, daß
• zwei Kugeln der Sorte B so schwer sind wie eine Kugel der
Sorte A,
• drei Kugeln der Sorte C so schwer sind wie eine Kugel der
Sorte B,
• fünf Kugeln der Sorte D so schwer sind wie eine Kugel der
Sorte C.
Wieviele Kugeln der Sorte D sind so schwer wie eine Kugel der
19
Sorte A?
(e) Eine Familie bestehe aus Vater, Mutter, zwei Söhnen und zwei
Töchtern. Das Produkt des ganzzahligen Alters der weiblichen
Familienanghörigen beträgt 5291, das des ganzzahligen Alters der
männlichen Familienanghörigen beträgt 3913. Zwei Kinder der Familie sind Zwillinge. Sind nun diese Zwillinge gleichen oder verschiedenen Geschlechts?
• Analytische Rätsel V
Problem 18.
(a) Ein Zug fährt mit konstanter Geschwindigkeit über eine 225 m
lange Brücke in 27 sec, von der Auffahrt der Lokomotive auf die
Brücke bis zur Abfahrt des letzten Waggons von der Brücke. An
einem Fußgänger, der in Gegenrichtung unterwegs ist, fährt der
Zug in 9 sec vorüber. In dieser Zeit legt der Fußgänger 9 m zurück.
Wie lang ist der Zug und welche Geschwindigkeit hat er?
(b) x2 − x2 = x2 − x2 ⇒ (x + x)(x − x) = x(x − x) ⇒ x + x = x ⇒
20
2x = x ⇒ 2 = 1 Wo ist der Fehler?
(c) Führe ganzzahlige Divisionen durch. Wird der Dividend um 65
und der Divisor um 5 erhöht, so verändern sich Quotient und
Rest nicht. Wie lautet der Quotient?
(d) Ist es möglich, fünf aufeinander folgende positive ganze Zahlen
derart zu finden, daß die Summe der Quadrate der beiden größten
Zahlen der Summe der Quadrate der drei anderen Zahlen entspricht?
(e) Eine Flasche Wein kostet 9 Euro. Der Wein kostet 8 Euro mehr
als die Flasche. Wie teuer ist die Flasche?
(f) Ein Bauer baut auf einem Drittel seines Landes Weizen, auf einem Viertel Erbsen, auf einem Fünftel Bohnen und Mais auf den
restlichen 26 ha. Wie groß ist sein Land?
(g) Heini und Karl machen Rast. Einer der beiden packt fünf Würste,
der andere drei Würste aus. Egon stößt zu ihnen und will mitessen:
Ich bezahle meinen Anteil auch!“Einvernehmlich ißt jeder der
”
drei gleichviel. Egon bezahlt 8 Euro. Wie müssen Heini und Karl
die 8 Euro unter sich aufteilen?
(h) Ein Bauer hat 17 Kühe testamentarisch unter seinen Söhnen auf-
21
geteilt: der älteste bekommt die Hälfte der Kühe, der mittlere
ein Drittel und der jüngste ein Neuntel der Kühe. Es darf keine
Kuh getötet werden. Wie kann ein Nachbar bei der Aufteilung der
Kühe helfen?
• Brückenquerung
Problem 19.
(a) Vier Personen müssen nachts eine Hängebrücke überqueren. Die
Querung darf nur mit Taschenlampe durchgeführt werden. Es gibt
nur eine Taschenlampe mit maximale Leuchtdauer von einer Stunde. Auf der Brücke dürfen sich gleichzeitig maximal nur zwei Personen aufhalten. Die vier Personen brauchen für die Querung unterschiedlich viel Zeit: A 5 min, B: 10 min, C: 20 min, D: 25 min.
Die langsamere von zwei Personen bestimmt das Tempo. In welcher Reihenfolge müssen die Personen die Brücke überqueren, so
daß sie nach spätestens 60 min alle die andere Seite erreicht haben?
22
• Synthetische Rätsel I
Problem 20.
Das gleichseitige Dreieck kann in drei kongruente
Teildreiecke zerlegt werden.
Die L-förmige Fläche kann in vier kongruente (Lförmige) Teilflächen zerlegt werden.
Kann auch ein Quadrat in jetzt fünf kongruente
Teilflächen zerlegt werden?
Die sechs Geldstücke sollen so umgelegt werden,
daß sich zwei gerade, jeweils aus vier Münzen be(b)
stehende Reihen ergeben.
Die neun Punkte sollen durch vier gerade Linien
(c)
in einem Zug verbunden werden.
(d) Jeder der 30 Vasallen muß dem König 30 Goldmünzen zahlen. Wie
bekannt zahlt einer von ihnen mit 9 g- statt mit den geforderten
10 g-Münzen. Wie kann der König mit einer einzigen Wägung den
Betrüger feststellen?
(a)
2
1
2
1
23
• Synthetische Rätsel II
Problem 21.
(a) Drei Bauern ordern zusammen einen Pflug für 30 Taler. Jeder
bezahlt 10 Taler. Nach der Lieferung hält der Schmid den Preis
für zu hoch, 25 Taler seien angemessen. Der Lehrling soll 5 Taler
zurückerstatten. Der Lehrling kann 5 Taler nicht dritteln, gibt
daher jedem Bauern einen Taler zurück und behält 2 Taler. Jeder
Bauer hat dann also 9 Taler bezahlt, der Lehrling behält 2 Taler,
macht zusammen 29 Taler. Wo ist der 30. Taler?
(b) Aus sechs Streichhölzern baue man vier gleichseitige Dreiecke.
(c) Zehn Bäume sollen so gepflanzt werden, daß sich fünf gerade Reihen mit je vier Bäumen ergeben.
(d) Ein quadratischer Bierträger faßt 36 Flaschen. Ist es möglich, darin 14 Flaschen so anzuordnen, daß die Anzahl der Flaschen in jeder
Zeile und in jeder Spalte gerade ist?
24
• Synthetische Rätsel III
Problem 22.
(a) Multipliziere (x − a)(x − b) . . . (x − z) aus.
(b) Ein sehr schwerer Sessel soll umgestellt werden. Man kann ihn
aber nur um jede seiner Ecken um jeweils genau 90o drehen. Kann
er am Ende genau neben seiner ursprünglichen Position stehen,
wobei die Rückenlehne wieder hinten ist?
(c) Von einem Schachbrett werden zwei gegenüber liegende Eckfelder
entfernt. Kann man das modifizierte Schachbrett vollständig mit
Domino-Steinen abdecken, die jeweils zwei Schachfelder überdecken?
(d) Um eine zweistellige Zahl z5 mit Endziffer 5 zu quadrieren, multipliziert man z mit z + 1 und schreibt hinter das Ergebnis 25. So
ergibt sich z.B. 752 = (7 · 8) · 100 + 25 = 5625. Funktioniert der
Trick immer?
• Synthetische Rätsel IV
Problem 23.
25
(a) Ein Quader soll in 27 kongruente kleine Quader zersägt werden.
Dies ist mit sechs Schnitten möglich. Geht das auch mit weniger
Schnitten?
Bauen Sie ein Kartenhaus wie nebenstehend
(b)
angedeutet mit 47 Etagen. Wieviele Karten
brauchen Sie?
(c) Finde mit drei Wägungen auf einer Balkenwaage ohne Gewichte
heraus, ob eine von 12 Gold Dublonen gefälscht und daher schwerer oder leichter als eine echte Dublone ist?
(d) Gibt es eine Folge von Zahlen, in denen jede der Ziffern 0 bis 9
nur einmal vorkommt und deren Summe gleich 100 ist?
1 floor
2 floors
3 floors
• Dialektisches Rätsel
Problem 24.
(a) Drei Gefangene werden entlassen, wenn sie folgendes Rätsel lösen:
sie werden im gleichseitigen Dreieck mit verbundenen Augen jeweils zueinander zugewandt aufgestellt. Hinter jedem von den
Dreien ist eines von drei weißen und zwei schwarzen Fähnchen
26
aufgebaut (zwei der fünf Fähnchen werden nicht gebraucht). Die
Augenbinden werden entfernt und diejenigen Gefangenen sollen
entlassen werden, die die Farbe des Fähnchens hinter ihnen richtig erraten. Die Gefangenen denken eine Weile sehr angestrengt
nach und nennen endlich nahezu gleichzeitig die richtige Farbe des
Fähnchens hinter jedem von ihnen. Wie das?
• Rätsel, 588
Problem 25.
(a) An einem Waldlauf nehmen 81 Personen teil, doppelt so viel Männer
wie Frauen. Die Anzahl der Kinder und Jugendlichen ist halb so
groß wie die Anzahl der Erwachsenen. Es sind doppelt so viele
Jugendliche wie Kinder. Wie viele Männer, Frauen, Jugendliche
und Kinder nehmen teil?
(b) VVVLLL symbolisiert eine Reihe von sechs Gläsern, drei vollen und
drei leeren.
Man bewege/berühre nur ein Glas (voll oder leer), um eine Reihe
27
von Gläsern zu bekommen, in der sich volle und leere Gläaser
abwechseln.
(c)
=
Man bewege nur ein Streichholz, um eine korrekte
Gleichung zu bekommen.
(d) Lokführer, Heizer und Schaffner eines Zuges heißen J., M. und B.,
aber nicht notwendig in dieser Reihenfolge. Drei Reisende im Zug
haben dieselben Namen, allerdings mit Doktortitel: Dr. J., Dr. M.
und Dr. B. Bekannt ist
1. Dr. B. wohnt in Charlottenburg.
2. Dr. J. verdient 5000Euro pro Monat.
3. Der Schaffner wohnt auf halber Strecke zwischen Charlottenburg
und Nürnberg.
4. Sein Nachbar, einer der Passagiere, verdient genau dreimal soviel
wie er.
5. Der Namensvetter des Schaffners wohnt in Nürnberg.
6. M. besiegt den Heizer im Schach.
Wie heißt der Lokführer?
(e) Robert sammelt Eidechsen, Käfer und Würmer. Er hat mehr Würmer als Eidechsen und Käfer zusammen. Insgesamt hat er 12 Exemplare mit 26 Beinchen. Wieviele Eidechsen besitzt Robert?
28
(f) Drei Männer haben jeweils zwei Jobs. Der Chauffeur hat den Musiker beleidigt. Musiker und Gärtner fischen zusammen mit Hans.
Der Maler leiht sich was vom Kaufmann. Der Chauffeur macht
der Schwester des Malers den Hof. Klaus schuldet dem Gärtner
20Euro. Joe schlägt Klaus und den Maler im Schach. Einer ist
Friseur. Keine zwei gehen derselben Beschäftigung nach. Wer hat
welche Berufe?
(g) Fünf Frauen sitzen um einen runden Tisch. Frau Oßwald sitzt
zwischen Frau Lutz und Frau Martin. Erika sitzt zwischen Katy
und Frau Neidlinger. Frau Lutz sitzt zwischen Erika und Alice.
Katy und Doris sind Schwestern. Bettina hat als linke Nachbarin
Frau Pieper, als rechte Nachbarin Frau Martin. Wer mit welchem
Vor- und Nachnamen sitzt wo am Tisch?
• Rätsel, 622
Problem 26.
(a) Gibt es genau 204 Quadrate auf einem Standard-Schachbrett?
29
(b) Indem man mehrere Geraden durch ein Quadrat legt, zerlegt man
dieses in disjunkte Gebiete. Wieviele Farben braucht man für das
Einfärben der Gebiete mindestens, wenn keine zwei sich nicht nur
in einem Punkt berührenden Gebiete dieselbe Farbe tragen?
(c) Die Damen A., E., I., O. und U. arbeiten in einem Stern-förmigen
Büro mit Zentrale und Flügeln in jede der vier Himmelsrichtungen. Wege zwischen den Flügeln führen immer durch die Zentrale.
Bevor A. und ich unsere Arbeitsplätze getauscht haben, lag mein
Raum nördlich von dem von O., die östlich von U. arbeitet, welche
westlich von E. arbeitet. Vordem hat A. östlich von I. gearbeitet.
Damals mußte A. in der Zentrale in den rechten Gang einbiegen,
wenn sie E. besuchen wollte. Ich ging geradeaus, wenn ich A. besuchen wollte. Wer arbeitet wo? und wer ist ich?
• Labyrinth, 652
Problem 27.
(a) Gesucht ist der kreuzungsfreie Weg durch das Labyrinth zurück
30
zu Ausgangspunkt.
• Rätsel, 680
Problem 28.
(a) Wie kann man mit einer 7-min- und einer 11-min-Sanduhr die Zeit
für ein 15min-Ei abmessen?
• Rätsel, 708
Problem 29.
(a) Herr Pünktlich stellt sein Uhr am Samstag um 12h. Am Sonntag
stellt er um 12h fest, daß seine Uhr 6min nachgeht. Herr Pünktlich
vergißt, seine Uhr zu stellen. Welche Zeit zeigt seine Uhr am Monatg um 8h an?
(b) Eine Frau kauft beim Bäcker die Hälfte aller Brote und ein halbes
Brot. Ein zweite Frau kauft danach die Hälfte aller restlichen Brote
und ein halbes Brot. Eine dritte Frau kauft danach die Hälfte
31
aller nunmehr restlichen Brote und ein halbes Brot. Jetzt sind alle
Brote verkauft. Wieviele Brote hat der Bäcker insgesamt verkauft?
(c) Ein automatischer Stempel druckt beginnend mit 0 eine fortlaufende Zahl pro Sekunde. Wie oft wird die Ziffer 1 in der ersten
Viertelstunde gedruckt?
• Rätsel, 734
Problem 30.
(a) Wenn sich Demonstranten in Zweier-, Dreier-, Vierer- bis hin zu
Zehner-Reihen aufstellen, fehlt immer genau ein Demonstrant.
Wieviel Demonstranten demonstrieren, wenn es insgesamt weniger
als 5000 sind?
(b) Meine Schwester, Du hast genauso viele Brüder wie Schwestern!“
”
Mein Bruder, Du hast zweimal mehr Schwestern als Brüder!“
”
Wieviele Kinder hat diese Familie?
(c) Zwei Schwestern haben vier Jahre Altersunterschied. Die Differenz
der Kubik-Zahl des Alters der Ersten und der Kubik-Zahl des
32
Alters der Zweiten beträgt 988. Wie alt sind die Schwestern?
• Rätsel, 750
Problem 31.
(a) Auf einem großen Hof mit gleich vielen Kühen, Schweinen, Pferden
und Kaninchen bricht eine Seuche aus. Alle beklagen sich:
Vater: Jede fünfte Kuh ist gestorben. Mutter: Es gibt genauso viele
tote Pferde wie überlebende Schweine. Sohn: Der neue neue Anteil
von Kaninchen (unter den Überlebenden) beträgt 5/14. Oma: Der
Tod hat keine Tierart verschont.
Beweise, daß die Oma sich geirrt hat!
• Rätsel, 772
Problem 32.
(a) Eine Flasche Wein kostet 9 Euro. Der Wein kostet 8 Euro mehr
als die Flasche. Wieviel kostet nur die Flasche?
33
(b) Ein Vater im Sterben vermacht seinen Söhnen 30 Fässer, zehn
volle, zehn halbvolle und zehn leere. Wie müssen Wein und Fässer
aufgeteilt werden, damit jeder der drei Söhne gleichviel Wein und
gleichviele Fässer bekommt?
34
3. Prim-Zahlen
In den modernen Verfahren der Kryptographie spielen Prim-Zahlen
eine entscheidende Rolle. Prim-Zahlen haben aber auch schon seit
Jahrtausenden nicht nur Mathematiker herausgefordert. So gibt es
beispielsweise seit langem Versuche, Prim-Zahlen algorithmisch zu erzeugen.
• Fermat-Zahlen
Problem 33. Die Fermat1 -Zahlen sind definiert durch
n
F (n) = 22 + 1
(a) Fermat ging fälschlicherweise davon aus, auf diese Weise (alle?)
Prim-Zahlen aufzählen zu können.
1
Pierre Fermat (1601-1665)
www-history.mcs.st-and.ac.uk/history/Biographies/Fermat.html
Abschnitt 3: Prim-Zahlen
35
• Euler-Zahlen
Problem 34. Die Euler2 -Zahlen sind definiert durch
E(n) = n2 − n + 41
(a) Nur die ersten 40 Euler-Zahlen sind prim.
2
Leonhard Euler (1707-1783)
www-history.mcs.st-and.ac.uk/Biographies/Euler.html
Abschnitt 3: Prim-Zahlen
36
• Mersenne-Zahlen
Problem 35. Die Mersenne3 -Zahlen sind definiert durch
M (n) = 2n − 1
(a) Die Mersenne-Zahlen sind teilweise prim. Es gilt
n nicht prim ⇒ M (n) nicht prim
Leider ist M (n) nicht notwendig prim, falls n prim ist, wie schon
kleine vierstellige (< 212 ) Mersenne-Zahlen zeigen.
3 Marin
Mersenne (1588-1648)
www-history.mcs.st-and.ac.uk/Biographies/Mersenne.html
37
4. Rechnen mit Divisionsresten
• Entscheidend ist, was übrig bleibt
Die Modulo-Arithmetik, also das Rechnen mit Divisionsresten, spielt
(nicht nur) in der Kryptographie eine entscheidende Rolle.
n mod m = r ⇐⇒ n = v m + r für n, v ∈ Z, m, r ∈ N und 0 ≤ r < m
Problem 36.
(a) Welchen Wochentag haben wir in n Tagen?
(b) Welchen Wochentag hatten wir vor n Tagen?
(c) Wie wird das UNIX-Datum berechnet, wenn intern ein Zähler die
Sekunden seit dem 1.1.1970 0h zählt?
Abschnitt 4: Rechnen mit Divisionsresten
38
• mit Resten rechnen
n ≡ r (mod m) ⇐⇒ m | (n − r) ⇐⇒ m | n − r
n ≡ r (mod m) ⇐⇒ n − r = v · m für m, r, v ∈ N und 0 ≤ r < m
Problem 37.
(a) Zusammenhang von n mod m = r
und n ≡ r (mod m)
(b) Additivität, Multiplikativität:
n1 ≡ r1 (mod m)
(n1 ± n2 ) ≡ (r1 ± r2 ) (mod m)
⇒
n2 ≡ r2 (mod m)
(n1 · n2 ) ≡ (r1 · r2 ) (mod m)
(c) skalare Vielfache, Potenzen
c · n ≡ c · r (mod m) für jedes c ∈ N
n ≡ r (mod m) ⇒
np ≡ rp (mod m) für jedes p ∈ N
(d) Transitivität
r ≡ s (mod m), s ≡ t (mod m) ⇒ r ≡ t (mod m)
?
39
• geschickt mit Resten rechnen
s(n) =
P∞
i=0 zi
bezeichne die Quersumme von n =
P∞
i=0 zi 10
i
.
Problem 38. Lieber fix Teilbarkeit testen anstatt zu dividieren!
(a) 3 | s(n) ⇒ 3 | n sowie 9 | s(n) ⇒ 9 | n
Berechne
3, 1234567890 mod 9 usw.
P∞
P∞ 1234567890 mod
(b) 11 | i=o (−1)i zi ⇒ 11 | i=0 zi 10i
Berechne 1234567890 mod 11 usw.
(c) Die letzte Ziffer der 10-stelligen ISBNummern ist eine Prüfziffer,
P9
und zwar n mod 11, wenn n = i=1 i · zi die gewichtete Summe
1·z1 +2·z2 +. . .+9·z9 der ersten neun Ziffern z1 . . . z9 bezeichnet.
(Falls
P∞ n mod 11 = 10, so repräsentiert ein X die Prüfziffer.)
(d) 7| i=0 z7i+0P+ 3z7i+1 + 2z7i+2 − z7i+3 − 3z7i+4 − 2z7i+5 + z7i+6
∞
⇒ 7 | i=0 zi 10i
Berechne 1234567890 mod 7 usw.
(e) Parity, ECC, CRC, RSC, . . . ?
• Euklid &
40
der kleine Fermat
Problem 39. ggT(a, b) bezeichne den größten gemeinsamen Teiler,
ggT von a ∈ N und b ∈ N, d.h. ggT(a, b) = d ∈ N mit d | a und d | b
sowie der Maximalität, i.e. d0 | a, d0 | b ⇒ d0 | d.
(a) Für a, b ∈ N gilt ggT(a, b) = ggT(a, b mod a) = ggT(b, a mod b)
(b) Iteration liefert den (abbrechenden) Euklid4 schen Algorithmus.
(c) Fermat5 s kleiner Satz: Wenn p prim ist, dann gilt
ap−1 ≡ 1 (mod p)
für jedes zu p teilerfremde a ∈ N, d.h. a 6∈ pN oder ggT(a, p) = 1
Umkehrung (Kontraposition):
an−1 6≡ 1 (mod n) für ein a ∈ N ⇒ n ist zusammengesetzt!
(d) Es gilt die Implikation
nicht deren Umkehrung
4
5
n prim ⇒ n | 2n−1 − 1
n prim ⇐ n | 2n−1 − 1
Euklid von Alexandria (ca 325-265)
Pierre Fermat (1601-1665)
www-history.mcs.st-and.ac.uk/Biographies/Euclid.html
www-history.mcs.st-and.ac.uk/Biographies/Fermat.html
41
• Fermat, Euler und mehr
Problem 40. Die Euler6 -sche ϕ-Funktion ist definiert durch
ϕ(n) = |{m ∈ N : m < n, ggT(m, n) = 1}|
(a)
(b)
(c)
(d)
Für primes p gilt
ϕ(p) = p − 1.
Für primes p gilt
ϕ(pk ) = pk − pk−1 = (p − 1)pk−1 .
Für teilerfremde r und s gilt
ϕ(r · s) = ϕ(r) · ϕ(s).
Die Primfaktorzerlegung von n erlaubt also eine ganz einfache
Berechnung von ϕ(n). Für prime p und q gilt also insbesondere
ϕ(p · q) = ϕ(n) = n − (p + q) + 1 = (p − 1)(q − 1) für n = p · q
(e) Satz von Euler, EFT7 :
aϕ(n) ≡ 1 (mod n)
für jedes n ∈ N und jedes zu n teilerfremde a.
6
1736
7 Euler-Fermat-Theorem,
42
• Chinesisches
Problem 41.
(a) Chinesischer Restsatz: m1 , m2 , . . . , mn ∈ N seien paarweise
teilerfremd. Um alle Lösungen x ∈ N mit
x ≡ ri (mod mi ) für i = 1, . . . , n
Qn
zu finden, bestimmt man m = i=1 mi und bi = m/mi sowie xi
mit xi bi = 1 mod mi , also xi als das (modulo mi )-Inverse zu bi
für i = 1, . . . , n. Dann gilt:
n
X
x≡
(xi bi ri ) (mod m)
i=1
(b) Falls p und q teilerfremd sind, so gilt
x = y mod p und x = y mod q
⇒
x = y mod (pq)
(c) Das Alter etwa von Party-Gästen läßt sich aus den erfragten Resten bei Division durch 3, 5 und 7 erschliessen.
43
• Galois-Körper GF(p)
Problem 42. Gewöhnlich betreibt man Arithmetik in Körpern wie
Q, R und C mit unendlich vielen Elementen. Etwa in der Kryptographie sind aber nur Körper mit endlich vielen Elementen relevant.
Zur Erinnerung, ein Körper ist eine Menge K von Elementen zusammen
mit zwei Operationen, nämlich Addition + und Multiplikation ·, so daß
(K, +) (mit Null-Element 0) und (K ∗ , ·) = (K \ {0}, ·) (mit Eins-Element
1) kommutative Gruppen sind und die üblichen Distributiv-Gesetze gelten:
(K, +) ist kommutative Gruppe
(K ∗ , ·) ist kommutative Gruppe
∀a,b∈K a + b = b + a ∈ K
∀a,b∈K ∗ a · b = b · a ∈ K ∗
∃0∈K ∀a∈K a + 0 = 0 + a = a
∃1∈K ∗ ∀a∈K ∗ a · 1 = 1 · a = a
∀a∈K ∃−a∈K a + (−a) = (−a) + a = 0 ∀a∈K ∗ ∃a−1 ∈K ∗ a · a−1 = a−1 · a = 1
a · (b + c) = a · b + a · c
(a) Wie sind Addition und Multiplikation in GF(2) = {0, 1}, dem Galois8 -Körper der Ordnung 2, d.h. mit 2 Elementen, zu definieren?
(b) Wie sind Addition und Multiplikation in GF(3) = {0, 1, 2}, dem
8
Evariste Galois (1811-1832)
www-history.mcs.st-andrews.ac.uk/Biographies/Galois.html
44
Galois-Körper der Ordnung 3, zu definieren?
(c) Wie sind Addition und Multiplikation in GF(5) = {0, 1, 2, 3, 4},
dem Galois-Körper der Ordnung 5, zu definieren?
(d) Wie kann diese Vorgehensweise für GF(p) = {0, 1, 2, . . . , p − 1},
Galois-Körper der primen Ordnung p, verallgemeinert werden?
Und warum scheitert dieses Verfahren für GF(pq) mit primen p
and q, d.h. für GF(m) mit zusammengesetztem m ?
45
• Galois-Körper GF(pn )
Problem 43. Sei p prim und n ∈ N. Wenn man GF(pn ) auffaßt als
Teilmenge von P(n), der Menge aller Polynome der Ordnung n, d.h.
vom Grad n − 1, mit Koeffizienten in GF(p), sogenannte Polynome
über GF(p), können Polynome über GF(p) wie üblich addiert werden.
(a) Was ist dann GF(pn ), + ?
(b) Was passiert, wenn zwei Polynome r, s ∈ GF(pn ) als Polynome
über GF(p) multipliziert werden?
(c) Angenommen, das Produkt zweier Polynome r, s ∈ GF(pn ) sei
definiert als Rest des Produktes der beiden Polynome über GF(p)
bei Division durch ein Polynom m. Für welche Polynome m liegt
jedes dieser so definierten Produkte notwendig wieder in GF(pn ) ?
(d) Welche Polynome m(x) müssen ausgeschlossen werden, will man
garantieren, daß Produkte nicht-verschwindender Faktoren nicht
selbst verschwinden?
(e) Warum ist etwa m1 (x) = x2 + 1 ein reduzibles und m2 (x) =
x2 + x + 1 ein irreduzibles Polynom über GF(2) ?
46
Problem 44.
(a) Wie sehen die Multiplikation und die Bestimmung inverser Elemente in GF(22 ) mit m(x) = x2 + x + 1 aus?
(b) Sei m(x) ein irreduzibles Polynom über GF(p) mit Grad n. Sei
eine Multiplikation für r, s ∈ GF(pn )∗ durch
r · s := r(x) · s(x) mod m(x)
definiert. Was ist dann GF(pn )∗ , · ?
(c) Wie berechnet man die inversen Elemente in GF(pn ) ?
(d) Wieviele irreduzible Polynome über GF(p) von gegebenem (kleinem) Grad gibt es?
(e) Welche Rolle spielt die Wahl des irreduziblen Polynoms m(x) über
GF(p) vom Grad n − 1 für den konstruierten Körper GF(pn ) ?
(f) Welche Elemente erzeugen z.B. GF(22 )∗ oder GF(23 )∗ ?
(g) Wie kann die Zyklizität von GF(pn )∗ genutzt werden, um die Multiplikation in GF(pn )∗ zu beschleunigen?
(h) Wie kann die Zyklizität von GF(pn )∗ genutzt werden, um die Invertierung in GF(pn )∗ zu beschleunigen?
47
5. Kryptographie
• Caesar und Kohorten
Problem 45.
Die Buchstaben des lateinischen Alphabetes seien von 0 bis 25 durchnummeriert!
(a) Caesar9 - Verschlüsselung:
Klar-Text x1 x2 x3 . . . Buchstaben-weise mit Schlüssel k per
y = (x + k) mod 26 in Geheim-Text y1 y2 y3 . . . chiffrieren,
Geheim-Text y1 y2 y3 . . . Buchstaben-weise mit Schlüssel k per
x = (y − k) mod 26 in Klar-Text x1 x2 x3 . . . dechiffrieren.
Ein Geheim-Text laute wklvlvdwrsvhfuhwphvvdjh.
(b) Wieviele Schlüssel gibt es? Wie groß ist der Schlüsselraum?
Wie hoch ist die Verschlüsselungssicherheit?
9 Gaius
Julius Caesar (100-44 v.Chr.)
Abschnitt 5: Kryptographie
48
• Caesar generell
Problem 46.
(a) Unter welcher Bedingung ist y = (kx) mod m eine brauchbare
Verschlüsselungsvorschrift?
(b) Verschlüsselt wird mit y = (k x) mod m .
Entschlüsselt wird mit x = (k inv y) mod m . Mit welchem k inv ?
(c) Kombiniert man beide Verfahren, so wird mit
y = (k1 x + ko ) mod m verschlüsselt und mit
x = (k10 y + ko0 ) mod m entschlüsselt. Mit welchen k10 und ko0 ?
(d) Wieviele Schlüssel gibt es? wie groß ist der Schlüsselraum?
49
• Vigenère und Konsorten
Problem 47.
(a) Vigenère10 -Verschlüsselung:
Klar-Text x1 x2 x3 ... Buchstaben-weise mit Schlüssel ko k1 ...kl−1
per yi = (xi + ki mod l ) mod 26 in Geheim-Text y1 y2 y3 ... chiffrieren,
Geheim-Text y1 y2 y3 ... Buchstaben-weise mit Schlüssel ko k1 ...kl−1
per xi = (yi − ki mod l ) mod 26 in Klar-Text x1 x2 x3 ... dechiffrieren.
Ein Geheim-Text laute dlgcmqkxmzwcmvcdqccwyqi.
(b) Wieviele Schlüssel gibt es? wie groß ist der Schlüsselraum?
10
Blaise de Vigenère (1523-1596)
raphael.math.uic.edu/~jeremy/crypt/contrib/deepak.html
50
• tarnen, tauschen und ...
Problem 48. Für das Caesar- und das Vigenère-Verfahren ist charakteristisch, daß aufgrund einer (Caesar) oder mehrerer (Vigenère)
eineindeutiger Abbildungen f : A → A des verwendeten Alphabetes
A jeder Buchstabe des Klartextes ersetzt wird ((monoalphabetische)
Substitution). Derartige Abbildungen f heißen Permutationen.
(a) Das lateinische Alphabet A = {A, B, . . . , Z} hat 26 Buchstaben.
Wieviele Permutationen von A gibt es?
(b) Liefern Permutationen neue Verschlüsselungsverfahren, die wesentlich besser als das Caesar- oder das Vigenère-Verfahren sind?
(c) Wie sinnvoll ist es, Texte dadurch zu verschlüsseln, daß man die
Klartextbuchstaben nur umstellt, also permutiert?
51
• DES
Problem 49. Data Encryption Standard, DES [28] ist ein Blockorientiertes, symmetrisches (identische Schlüssel für Ver- und Entschlüsselung) Verschlüsselungsverfahren, das aus Substitutionen und
Permutationen besteht. www.itl.nist.gov/fipspubs/fip46-2.htm
(a) Der DES-Algorithmus führt auf jedem 64bit-Block des Klartextes
nacheinander eine initiale bit-Permutation P , weitere Operationen
und schließlich P inv aus. DES spezifiziert nun P als
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
P =
. Wie lautet P inv ?
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
(b) Die weiteren Operationen chiffrieren jeweils linke und rechte 32bitHälfte eines 64bit Blocks (L, R) mit 32-bit Schlüssel K per
fK (L, R) = (R, L ⊕ K)
inv
fK
(L, R)
wo ⊕ Addition modulo 2 bezeichnet
= ? Inwiefern sind diese Operationen Substitutionen?
(c) Was für eine Sorte Verschlüsselungsverfahren ist bis hier durch
52
L := P inv ◦ fK16 ◦ fK15 ◦ . . . ◦ fK2 ◦ fK1 ◦ P definiert? mit welchen
Konsequenzen?
(d) Letzter Baustein im DES ist ein confusion/diffusion11 -Verfahren,
implementiert durch die sogenannten substitution boxes, S-Boxen:
jede Block-Hälfte à 32bit wird durch Verdoppeln (je nach Runde) bestimmter bits auf 48bit erweitert: insgesamt acht S-Boxen
S1 , . . . , S8 verschlüsseln jeweils 6bit input zu 4bit output, z.B. S5
S5
mittlere vier input bits
äußere
2 bits
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
00
01
10
11
0010
1110
0100
1011
1100
1011
0010
1000
0100
0010
0001
1100
0001
1100
1011
0111
0111
0100
1100
0001
1100
0111
1101
1110
1011
1101
0111
0010
0110
0001
1000
1101
1000
0101
1111
0110
0101
0000
1001
1111
0011
1111
1100
0000
1111
1100
0101
1001
1101
0011
0110
1100
0000
1001
0011
0100
1110
1000
0000
0101
1001
0110
1110
0011
s.a. www.itl.nist.gov/fipspubs/fip46-2.htm oder z.B. auch
www.kuno-kohn.de/crypto/crypto/des.htm für alle acht DES
S-Boxen. Wie groß sind die look up Tabellen für die acht S-Boxen?
Wie groß wäre die look up Tabelle für die durch die S-Boxen implementierte 32bit Substitution? Wie sieht die inverse S-Box aus?
11
Claude E. Shannon (1916-2001)
www-history.mcs.st-andrews.ac.uk/Biographies/Shannon.html
53
Problem 50. Seit seiner Veröffentlichung war die Sicherheit des Data
Encryption Standard, DES umstritten, vgl. z.B.
http://en.wikipedia.org/wiki/Data Encryption Standard.
Die in der Mitte der 1990er Jahre demonstrierte Unsicherheit des DES
machte Verbesserungen insbesondere für hoch sicherheitskritische Anwendungen notwendig.
(a) Was ist die effektive Länge der DES-Schlüssel? Wie groß ist also
der DES-Schlüssel-Raum?
(b) Triple DES, TDES oder Triple Data Encryption Algorithm, TDEA
besteht aus dreimaligem DES mit drei Schlüsseln
TDESK3 ,K2 ,K1 (x) = DESK3 DESinv
K2 DESK1 (x)
Welche Bedingung garantiert, daß mehrfache DES-Verschlüsselungen
(wie etwa TDEA) tatsächlich sicherer als DES sind?
(c) Was ist die effektive Länge der TDEA-Schlüssel? Wie groß ist also der
TDEA-Schlüssel-Raum?
(d) Wann und wodurch wurde DES bzw. TDEA abgelöst?
54
• öffentliche Schlüssel?
Problem 51. Symmetrische Verschlüsselungsverfahren setzen voraus, daß
der (für Ver- und Entschlüsselung identische) Schlüssel dem Empfänger über
einen sicheren Kanal übermittelt werden kann – ein Widerspruch in sich!
Asymmetrische Verschlüsselungsverfahren mit Paaren aus öffentlichen
und geheimen Schlüsseln (public key encryption12 ) bieten Abhilfe.
(a) Für jeden Teilnehmer A, B, C, . . . sei ein öffentlicher Schlüssel und damit ein öffentliches Verschlüsselungsverfahren fA , fB , fC , . . . bekannt.
Jeder Teilnehmer A, B, C, . . . halte dagegen seinen geheimen Schlüssel
A−1 , B −1 , C −1 , . . . und damit sein persönliches Entschlüsselungsver−1
−1
fahren fA
, fB
, fC−1 , . . . streng geheim.
Bob kann seiner Alice etwa x mitteilen, indem er ihr die verschlüsselte Nachricht fA (x) schickt. Nur Alice kann diese Nachricht mit Hilfe von fA−1 zu x = fA−1 (fA (x)) entschlüsseln.
Worauf beruht die Sicherheit dieser public key Verfahren?
12 Whitfield Diffie, Martin Hellman: New Directions in Cryptography;
IEEE Trans. Inform. Theory, IT-22, 6, Nov 1976 pp.644-654
55
• RSA
Problem 52. Das RSA13 -Verfahren, ein Verschlüsselungsverfahren
mit öffentlichen Schlüsseln14 , ist wie folgt zu implementieren.
Seien p und q große Primzahlen und n = p·q, also ϕ(n) = (p−1)(q−1).
Verschlüsselt (encryption) wird per
y = xe mod n mit öffentlichen Schlüsseln e, so daß ggT e, ϕ(n) = 1.
Entschlüsselt (decryption) wird per
x = y d mod n mit geheimen Schlüsseln d, so daß e d = 1 mod ϕ(n).
(a) Zeige: fe : x → xe mod n ist eine trapdoor Funktion.
(b) Worauf beruht die Sicherheit des RSA-Verfahrens?
(c) fe−1 oder eben fd wird zum Signieren von Botschaften verwendet.
Wenn Alice ihre Botschaft digital signiert, kann Bob sicher sein,
daß die empfangene Botschaft y auch wirklich von Alice stammt.
13 R. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures
and public key cryptosystems; Communications ACM, 21 (1978), 120-126
14 public keys
• AES
56
A. Hofmeier, AES – Eine Einführung in Kryptographie
10
rechts weitergegangen und wieder oben angefangen.
Problem 53. Der 2000 verabschiedete Advanced Encryption Standard, AES ist der Nachfolger des DES. Um jeden Verdacht der Konspiration von Standardisierungsgremium (NIST) und Entwicklern (IBM
im Fall von DES) vorzubeugen, ist der Standard als Ergebnis eines öffentlichen Wettbewerbes
verabschiedet worden. AES stellt einen
In der folgenden graphischen Darstellung wird von einer Blockgröße von 128 Bit
ausgegangen. Die Blöcke ließen sich allerdings in Vier-Byte-Schritten (32 Bit)
Spezialfall des Rijndael-Verfahrens
[26]
bis auf 256 Bit ausweiten. Dasselbe
gilt fürdar.
den Schlüssel. Daten-Blockgröße
0
4
8
12
0
4
8
12
16
20
24
28
1
5
9
13
1
5
9
13
17
21
25
29
2
6
10
14
2
6
10
14
18
22
26
30
3
7
11
15
3
7
11
15
19
23
27
31
128 Bit-Block (16-Byte)
256 Bit-Block (32 Byte)
und Schlüssel-Block-Größe sind vollkommen unabhängig voneinander. Im AES-
Standard sind allerdings lediglich Datenblockgrößen von
128 Bit und Schlüssel(a) AES ist eine Verschlüsselungsverfahren
welchen
Typs?
blocklängen von 128, 192 und 256 Bit vorgesehen. Dies ändert nichts daran, dass
der Rijndael-Algorithmus mehr kann, was aber nicht notwendiger implementiert
(b) Was sind die charakteristischen
Kenngrößen
von AES?
sein muss, wenn auf AES Bezug genommen
ist.
(c) Worin besteht eine
Verschlüsselungsrunde
Die graphische
Darstellung verdeutlicht den Fluss der Daten:von AES?
k(0)
AddRoundKey(
)
k(1...)
SubByte()
ShiftRows()
}
}
Round()
k(n)
MixColums()
FinalRound()
Adaptiert von Daemen und Rijmen (2002).
3.3.1
Anzahl der Runden
Wie oben ersichtlich, wird die Funktion Round() N mal ausgeführt. Wobei N von
der Schlüssel- und der Daten-Block-Größe abhängt. Die folgende Tabelle stellt
die Länge des Schlüssels der Länge des Datenblockes gegenüber und gibt für jede
Kombination eine Anzahl von Runden an. Alle fett dargestellten Fälle sind durch
57
Problem 54. Die Bestandteile einer Runde seien nun der Reihe nach
untersucht. Bezeichnungen wie in
csrc.nist.gov/publications/fips/fips197/fips-197.pdf
(a) SubBytes(): Wie ist diese Substitution spezifiziert? Wie wird sie
mit einer S-Box implementiert? Wie wird die Substitution invertiert?
(b) ShiftRows(): Wie ist die Permutation der Zeilen des als 4 × 4Byte-Matrix angeordneten Blocks implementiert? Wie wird diese
Transformation invertiert?
(c) MixColumns(): Wie werden die Spalten des als 4 × 4-Byte-Matrix
angeordneten Blocks transformiert? Wie wird diese Transformation invertiert?
(d) AddRoundKey(): Wie werden die Spalten mit Teilen des expandierten Schlüssels ’XORed’ ? Wieso stimmt diese Transformation
mit ihrer Inversen überein?
58
• Elliptische Kurven über R
Problem 55. Um Elliptic Curve Cryptography, ECC einzuführen, ist
hilfreich, zunächst sogenannte elliptische Kurven y 2 = x3 +ax+b über
R, d.h. Kurven im R2 mit reellen Koeffizienten a, b ∈ R zu betrachten.
(a) Welche geometrischen Eigenschaften haben elliptische Kurven E =
E(R) = Ea,b (R) über R ? Was passiert für x → +∞ ?
(b) Welche Nullstellen hat der Radikand x3 + ax + b einer elliptischen
Kurve E = E(R) = Ea,b (R) über R?
(c) Unter welcher Bedingung hat der Radikand einer elliptischen Kurve E = E(R) = Ea,b (R) über R keine mehrfachen Nullstellen?
(d) Eine nicht vertikale, nicht tangentiale Gerade schneide eine elliptische Kurve E = E(R) = Ea,b (R) über R mindestens zweimal.
Warum schneidet dann die Gerade die Kurve E dreimal?
(e) Gegeben P = (xP , yP ) und Q = (xQ , yQ ) mit xP 6= xQ auf einer elliptischen Kurve E über R. Wie lauten die Koordinaten
des unter obigen Bedingung existierenden dritten Schnittpunktes
R = (xR , yR ) auf E und auf der Geraden durch P und Q ?
59
Problem 56. Man spezifiziert eine Addition für Punkte P und Q auf
einer elliptischen Kurve E = Ea,b (R) über R durch R := P + Q als
den Schnittpunkt der Geraden durch P und Q mit E, gespiegelt an
der x-Achse.
y
−R
Q
P
x
R
a = −3, b = 5
(a) Wie ist P + P in konsistenter Weise zu definieren?
(b) Wie kann man P + Q für xp = xQ und yP 6= yQ in konsistenter
Weise definieren?
(c) Was bedeutet dies für P +Q mit P = (xP , yP ) und Q = (xp , −yP )
und die Lösbarkeit von P + Q = R in Q für gegebene P, R ∈ E ?
(d) Welche Struktur auf E = Ea,b (R) definiert diese Addition?
60
• Elliptische Kurven über GF(p)
Problem 57. Elliptische Kurven E = Ea,b (R) über R sind für die
Kryptographie unbrauchbar. Stattdessen benutzt man elliptische Kurven E = Ea,b (F) über einem endlichen Körper F, z.B. F = GF(p) für
primes p.
(a) Wie ist P + Q auf E = Ea,b GF(p) zu definieren?
• Elliptische Kurven über GF(2m )
Problem 58. Unter Verwendung von F = GF(2m ), einem anderen
Typ endlicher Körper,
kann man Gruppen auf elliptischen Kurven
E = Ea,b GF(2m ) über GF(2m ) definieren, nämlich
y 2 + xy = x3 + ax + b
für a, b ∈ GF(2m )
(a) Warum kann man jetzt y 2 = x3 + ax+ b nicht länger benutzen?
(b) Wie ist P + Q auf E = Ea,b GF(2m ) zu definieren?
61
• Elliptic Curve Cryptography, ECC
Problem 59. Elliptic Curve Cryptography, ECC nutzt die GruppenStruktur auf elliptischen Kurven E = Ea,b (F) über einem endlichen
Köper F zusammen mit einem geeigneten Generator-Punkt G ∈ E.
Jeder Teilnehmer verfügt über einen geheimen Schlüssel r ∈ N und
einen öffentlichen Schlüssel Q ∈ E, wobei r eine Zufallszahl mit 1 <
r < card(< G >) ist und Q = rG gilt.
(a) ECC ist ein Verschlüsselungsverfahren welchen Typs? für welche
Anwendungen?
(b) Wie kann man eine ECC-basierte El-Gamal Ver-/Entschlüsselung
realisieren?
(c) Wie kann man einen ECC-basierten Diffie-Hellman Schlüssel-Austausch, ECDH realisieren?
(d) Wie kann man einen ECC-basierten Digitale Signatur Algorithmus, ECDSA realisieren?
62
6. Kompression
• Ausnutzen relativer Häufigkeiten
Problem 60.
Wenn die (relativen) Symbol-Häufigkeiten in einem Text a priori bekannt sind, kann man einen code so entwerfen, daß der code eines
Symbols um so kürzer ist je häufiger er vorkommt. Wir nennen solche
Kodierungen monoton. Damit einzelne codes nicht mit einem Sonderzeichen voneinander getrennt werden müssen, darf kein Code mit dem
Anfang eines anderen Codes übereinstimmen: Die Kodierung muß
Präfix-frei sein.
(a) Gegeben ein Alphabet s1 , s2 , . . . , sn mit Häufigkeit fi des Symbols
si , wobei f1 > f2 > . . . > fn for i = 1, . . . , n. Angenommen
ci = code(si ) = 01i−1 ∈ {0, 1}i . Was ist zu dieser Kodierung zu
sagen?
(b) Wie sind Präfix-freie Kodierungen mit Graphen darzustellen?
(c) Konstruiere eine monotone Präfix-freie Kodierung.
Abschnitt 6: Kompression
63
• Wörterbücher nutzen
Problem 61.
Idee von LZW15 ist es, Sender und Empfänger ein Wörterbuch für zu
sendende bzw. zu empfangende Buchstaben und Buchstabenkombinationen zusammen mit ihren Codierungen anzulegen und fortzuschreiben zu lassen.
(a) Bei Kompression wie Dekompression wird zunächst das Wörterbuch
mit den Buchstaben des zugrundeliegenden Alphabetes zusammen
mit ihren Codes initialisiert.
Bei der Kompression wird der Klar-Text Zeichen-weise eingelesen. PATTERN ist die jeweils längste Zeichenkette im Wörterbuch,
die mit den jüngsten eingelesenen Zeichen übereinstimmt. Bei der
Dekompression werden die Codes eingelesen. Zugleich wird das
Wörterbuch entsprechend erweitert.
15
Jacob Ziv and Abraham Lempel: A Universal Algorithm for Sequential Data
Compression; IEEE Transactions on Information Theory, May 1977
Terry Welch, ”A Technique for High-Performance Data Compression”, Computer,
June 1984
64
Kompression:
PATTERN = get input character
WHILE there are still input characters DO
CHARACTER = get input character
IF PATTERN+CHARACTER is in dictionary
PATTERN = PATTERN+character
ELSE
output the code for PATTERN
add PATTERN+CHARACTER to dictionary
PATTERN = CHARACTER
output the code for PATTERN
Dekompression:
Read oldCODE; output dict[oldCODE]
Read newCODE
PATTERN = dict[newCODE]
output PATTERN
CHARACTER = first character in PATTERN
add dict[oldCODE]+CHARACTER to dictionary
oldCODE = newCODE
(b) Der obige Algorithmus hat eine Schwachstelle:
65
66
7. Wahrscheinlichkeit & Intuition
• Karten & Ziegen
Problem 62.
(a) In einer Urne befinden sich drei Karten: eine auf beiden Seiten
rot, eine auf beiden Seiten blau und die letzte auf einer Seite rot,
auf der anderen blau.
Mit welcher Wahrscheinlichkeit P ist eine beliebig gezogene Karte
mit roter Oberseite auf der Unterseite blau?
(b) Hinter drei Türen sind je zwei Ziegen und ein Auto (als Hauptpreis) verborgen. Der Quizmaster weiß, wo.
Der Kandidat entscheidet sich für eine Tür. Der Quizmaster öffnet
eine andere Tür mit einer Ziege dahinter.
Steigert der Kandidat seine Gewinnchancen, wenn er seine ursprüngliche Wahl revidiert?
Abschnitt 7: Wahrscheinlichkeit & Intuition
67
• Algorithmen erzeugen Zufall?
Zufallszahlen spielen eine wichtige Rolle für Simulation, für (zero
knowledge) Authentifizierungsverfahren, usw. Kein Wunder, daß jede
höhere Programmiersprache Bibliotheksfunktionen wie ran, random
oder randomize bietet, die algorithmisch und daher deterministisch
sogenannte Pseudo-Zufallszahlen erzeugen.
Problem 63.
(a) Welche Eigenschaften unterscheiden Zufallszahlen neben der Eigenschaft, anscheinend zufällig zu sein (was auch immer das sein
mag)? Wie sind Zufallszahlen mit solchen vorgegebenen Eigenschaften aus geeigneten Standard-Zufallszahlen zu erzeugen?
(b) Wie sind Standard-Pseudo-Zufallszahlen schnell, also mit wenig
(Rechen-) Aufwand zu erzeugen?
(c)
xn+1 = (a xn + c) mod m,
mit
xo = 1
ist periodisch – warum? und mit welcher maximalen/minimalen
Periodenlänge?
Abschnitt 7: Wahrscheinlichkeit & Intuition
68
• Was ist zufällig am Zufall?
Kriterien für die Qualität von Pseudo-Zufallszahlen-Generatoren sind
zu entwickeln, insbesondere also für Generatoren von im Einheitsintervall gleichverteilten Zufallszahlen, und in Tests zu bewerten. Allerdings existiert keine Definition von Zufälligkeit. Daher kann es Tests
nur für bestimmte ’features’ von Zufälligkeit geben.
Problem 64.
(a) Wie ist zu testen, ob der Wertebereich gleichmäßig ausgeschöpft
wird?
(b) Wie ist die Zufälligkeit von Pseudo-Zufallszahlen anhand des Informationsgehaltes einer jeden erzeugten Ziffer zu testen?
(c) Wie ist die Zufälligkeit von Pseudo-Zufallszahlen anhand ihrer
Komprimierbarkeit zu testen?
(d) Wie ist die Zufälligkeit von Pseudo-Zufallszahlen anhand der gegenseitigen (Un-) Abhängigigkeit ihrer Ziffern zu testen?
69
8. Quellen und links
Einige Referenzen zur Spaß-Mathematik
[1] About.com: Recreational Mathematics;
http://math.about.com/od/recreationalmath
[2] Bild der Wissenschaft;
www.wissenschaft.de/ s. Spiele-Archiv
[3] Chlond, Martin: Integer Programming in Recreational Mathematics;
www.chlond.demon.co.uk/academic/puzzles.html
[4] Canadian Mathematical Society
www.math.ca/Recreation
[5] Dutch, Steven: Recreational Mathematics;
www.uwgb.edu/dutchs/RECMATH/recmath.htm
[6] Eppstein, David: Math Fun;
www.ics.uci.edu/~eppstein/recmath.html
[7] Flannery, Sarah: In Code – A Mathematical Journey; Profile
Books, 2000 ISBN 1-86197-222-9 2, 5, 6, 7, 8, 9, 10, 11
Abschnitt 8: Quellen und links
70
[8] Gardner, Martin: Mathematical recreations and many more titles;
s. book list, e.g.
http://thinks.com/books/gardner.htm
[9] Gilleland, Michael: Recreational Mathematics Links;
www.weblearn.hs-bremen.de/risse/MAI/docs/MichaelGilleland.html
[10] Google Directory - Science > Math > Recreations;
www.google.com/Top/Science/Math/Recreations
[11] Herold, Helmut, Lurz, Bruno, Wohlrab, Jürgen: Grundlagen der
Informatik; Pearson 2012 2, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33
[12] Journal of Recreational Mathematics, Editor: Charles Ashbacher
and Lamarr Widmer;
www.baywood.com/journals/
PreviewJournals.asp?Id=0022-412x
[13] Mathematical Association of America, MAA: Recreational Mathematics;
www.maa.org/BLL/recmath.htm
[14] Mathematikwettbewerb Känguru e.V.
www.mathe-kaenguru.de
s.a. www.weblearn.hs-bremen.de/risse/MAI/docs/
71
[15] Michon, Gérard P.: Recreational Mathematics;
www.numericana.com/answer/recreational.htm
[16] New Scientist: Physics & Math
www.newscientist.com/section/physics-math
[17] O’Connor, J.J., Robertson, E.F.: mathematical games and recreations;
www-groups.dcs.st-andrews.ac.uk/~history/
HistTopics/Mathematical games.html
[18] open directory project
dmoz.org/Science/Math/Recreations/
[19] Problem of the Week, s. e.g.
[20] Scientific American
s. puzzling adventures in single issues
www.google.com
www.sciam.com,
[21] Singmaster, David: The Unreasonable Utility of Recreational Mathematics;
anduin.eldar.org/~problemi/singmast/ecmutil.html
[22] Eugène Strens Recreational Mathematics Collection Database;
www.ucalgary.ca/lib-old/sfgate/strens
72
[23] Wilkinson, David: Recreational Mathematics Links;
www.scit.wlv.ac.uk/~cm1985/RecMaths.html
[24] Wolfram Mathworld: Recreational Mathematics;
mathworld.wolfram.com/topics/RecreationalMathematics.html
Einige Referenzen zur Zahlentheorie
[25] Forster, Otto: Algorithmische Zahlentheorie; Vieweg 1996 190,
197
Einige Referenzen zur Kryptographie
[26] Federal Information Processing Standards, FIPS: Advanced Encryption Standard (AES); Publication 197
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Advanced Encryption Standard Algorithm Validation List
http://csrc.nist.gov/cryptval/aes/aesval.html 56
[27] Daemen, Joan, Rijmen, Vincent: The Design of Rijndael – AES,
The Advanced Encryption Standard; Springer 2002
73
[28] Federal Information Processing Standards, FIPS: Data Encryption Standard (DES); Publication 46-3 http://csrc.nist.gov/
publications/fips/fips46-3/fips46-3.pdf 51
[29] Federal Information Processing Standards, FIPS: Digital Signature Standard (DSS) – DSA, RSA, and ECDSA algorithms; Publication 186-2
http://csrc.nist.gov/cryptval/dss.htm
[30] Hankerson, Darrel, Menezes, Alfred, Vanstone, Scott: Guide to
Elliptic Curve Cryptography; Springer 2004 267
[31] Oswald, Elisabeth: Introduction to Elliptic Curve Cryptography;
www.iaik.tugraz.at/aboutus/people/oswald/papers/
Introduction to ECC.pdf 261, 264, 267
[32] Standards for Efficient Cryptography Group, SECG: SEC1 – Elliptic Curve Cryptography;
www.secg.org/collateral/sec1 final.pdf 267
[33] Wagner, Neal R.: The Laws of Cryptography;
www.cs.utsa.edu/~wagner/lawsbookcolor/laws.pdf
74
Einige Referenzen zur Codierung und Kompression
[34] Dankmeier, Wilfried: Codierung; Vieweg 2001
[35] Nelson, Marc, Gailly, Jean-loup: The Data Compression Book;
2nd edition, M&T Books, New York, NY 1995
Einige Referenzen zur Wahrscheinlichkeit
[36] Bronstein, I.N. & Semendjajew, K.A. et al: (Teubner-) Taschenbuch der Mathematik; Teubner 2003 287
Selbstverständlich freue ich mich über jede Zusendung weiterer origineller Aufgaben oder besserer Lösungen.
Prof. Dr. Th. Risse, ZIMT 244,
www.weblearn.hs-bremen.de/risse
0049 (0)421 5905-5489
mailto: [email protected]
75
Problem 1(a)
4 = (5 − 3) + (5 − 3)
76
Problem 1(b)
1=3+3−5
77
Problem 1(c)
Beispielsweise 5 = 9 − 4, 3 = 4 + 4 + 4 − 9, . . .
78
Problem 1(d)
Es gibt keine Lösung!
79
Problem 2(a)
Sehen wir uns die Leistungsbilanz an:
Am 1. Tag erreicht er 300m, in der 1. Nacht fällt er zurück auf 100m
am 2. Tag erreicht er 400m, in der 2. Nacht fällt er zurück auf 200m
am 3. Tag erreicht er 500m, in der 3. Nacht fällt er zurück auf 300m
...
am 27. Tag erreicht er 2900m, in der 27. Nacht fällt er zurück auf
2700m
am 28. Tag erreicht er 3000m,
80
Problem 2(b)
A brauche für die 100m tA Zeiteinheiten, ZE. Seine Geschwindigkeit
ist also vA = 100/tA .
B brauche für die 100m tB ZE. Seine Geschwindigkeit ist also vB =
100/tB = 90/tA . Daher ist tA /tB = 0.9.
Die Geschwindigkeit von C ist vC = 90/tB = x/tA . Also ist x =
90tA /tB = 90 · 0.9 = 81m.
Der Erste A schlägt den Dritten C um 19m.
81
Problem 3(a)
36 = 22 · 32 . Wenn man 1-jährige Kleinkinder nicht vergißt, ergeben
sich folgende mögliche Kombinationen:
P
3. 2. 1.
1 1 36 38
1 2 18 21
1 3 12 16
1 4
9 14
1 6
6 13
2 2
9 13
2 3
6 11
3 3
4 10
Also bedurfte es nur bei der Summe 13 eines weiteren Hinweises. Ein
ältestes Kind gibt es nur, wenn die Familie zweijährige Zwillinge und
ein neunjähriges Kind hat.
82
Problem 4(a) poor man’s Lösung:
Die Katastrophe ereignet sich nach einer Stunde. Die Fliege hat also
75km zurückgelegt.
angeblich John von Neumann’s Lösung:
Sei sl die Position des ’linken’ Zuges, sr diejenige des ’rechten’ Zuges.
Die Fliege starte ’rechts’. t1 sei der Zeitpunkt des ersten Auftreffens
(auf den ’linken’ Zug), t2 sei der Zeitpunkt des zweien Auftreffens (auf
den ’rechten’ Zug), usw.
Dann gilt sl (t1 ) = 50t1 und 75 = (100 − sl (t1 ))/t1 . Damit ist 75t1 =
100 − 50t1 , 125t1 = 100 und endlich t1 = 4/5.
t/h
0
4/5
4/5 + 4/25
4/5 + 4/25 + 4/125
sl (t)/km
0
40
48
49.6
..
.
sr (t)/km
100
60
52
50.4
d/km
0
60
12
2.4
83
wobei d die Distanz bezeichne, die die Fliege zwischen zwei Auftreffen
zurückgelegt hat.
Also ist der Zeitpunkt der Katastrophe
∞
X
1
5
t∞ = 4
0.2i = 4
−1 =4
−1 =1
1 − 0.2
4
i=1
und die insgesamt zurückgelegte Flug-Strecke
4
4
4
75 + 75 + 75
. . . = 75km.
5
25
125
84
Problem 5(a)
sh (t) bzw. sr (t) bezeichne die auf dem Hinweg bzw. Rückweg zurückgelegte Distanz entlang der Reiseroute für jeden Zeitpunkt t zwischen
Sonnenaufgang 0 und Sonnenuntergang 1.
Sei d die Entfernung zwischen A und B. Dann ist sh (0) = 0, sh (1) = d,
sr (0) = d, sr (1) = 0.
Mit sh und sr ist auch δ(t) = sr (t) − sh (t) eine stetige Funktion von t.
Wegen der unterschiedlichen Vorzeichen von δ(0) = d und δ(1) = −d,
hat δ(t) mindestens eine Nullstelle to im Intervall [0, 1].
Für den Zeitpunkt to gilt sr (to ) = sh (to ).
Unter welchen Bedingungen gibt es mehrere solcher Punkte?
85
Problem 6(a) Acht Gleichungen in neun Unbekannten mit Beschränkung der Lösung auf die natürlichen Zahlen 1,. . . ,9.
Wir gehen schrittweise vor, um diejenigen acht der 9!=362880 Anordnungen zu selektieren, die magischen Quadraten entsprechen.
1. Das Element in der Mitte/Zentrum ist notwendigerweise 5.
n = 6, 7, 8 bzw. 9 scheiden aus, weil dann m = 9, 8, 7 bzw. 6
nicht platziert werden könnte.
2. Die 9 steht nicht in einer Ecke, also nicht im NO, NW, SW, SO.
Angenommen, o.B.d.A. NW=9. Dann wäre SO=1 und es blieben für die drei Zahlen 6,7 und 8 nur die zwei Positionen O
und S.
3. Sei o.b.d.A. W=9. Dann gilt entweder NW=2 und SW=4 oder
NW=4 und SW=2.
Angenommen, NW=3. Dann wäre auch SW=3. Die 3 darf aber
nur einmal vergeben werden.
Damit ergeben sich zwei der bis auf Symmetrie identischen acht magischen Quadrate
2
9
4
86
7
5
3
6
1
8
und
4
9
2
3
5
7
8
1
6
Wie sehen die übrigen sechs magischen Quadrate aus?
87
Problem 7(a)
Im Text kommt der Buchstabe e überhaupt nicht vor, dafür aber
jeder andere Buchstabe des Alphabetes mindestens einmal.
Entwerfen Sie einen vergleichbaren, möglichst kurzen, deutschen Text.
88
Problem 8(a)
Mit folgendem Verfahren ermittelt der Personalchef die Gehaltssumme ohne Kenntnis der individuellen Gehälter (auch die Mitarbeiter
bekommen keine Kenntnis vom Gehalt eines Kollegen):
1. Er wählt zufallig eine große, ’geheime’ Zahl k.
2. Er teilt k dem ersten Mitarbeiter der Abteilung mit. Dieser inkrementiert k um sein Gehalt und teilt die Summe dem zweiten
Mitarbeiter mit.
3. Nacheinander inkrementieren die Mitarbeiter die ihnen genannte Zahl um ihr Gehalt und teilen die Summe dem nächsten Mitarbeiter mit.
4. Der letzte, n-te Mitarbeiter inkrementiert seinerseits die ihm
genannte Zahl um sein Gehalt und teilt das Ergebnis g dem
Personalchef mit.
Das Durchschnittsgehalt ist dann (g − k)/n.
89
Problem 9(a)
Das Problem besteht darin, Alice zu ermöglichen, die Kiste auch zu
öffnen. Die beiden verabreden daher folgendes Verfahren.
1. Bob schickt Alice die mit seinem Schloß verschlossene Kiste.
2. Alice verschließt die mit Bobs Schloß gesicherte Kiste zusätzlich
mit ihrem Schloß und schickt sie an Bob zurück.
3. Bob entfernt sein Schloß und sendet die mit Alice’s Schloß gesicherte Kiste an Alice.
90
Problem 10(a)
Sie vereinbaren etwa per e-mail folgendes Verfahren:
1. Alice und Bob einigen sich auf die Verwendung einer geeigneten ’1-Weg’-Funktion f , d.h. einer eineindeutigen Funktion
f : N ⊃ D → W ⊂ N, so daß f (x) leicht und f inv (y) extrem
schwer, extrem aufwändig, in der Konsequenz also so gut wie
überhaupt nicht zu berechnen ist.
2. Etwa Alice beginnt, wählt ein (gerades oder ungerades) x ∈ D
und sendet Bob y mit y = f (x), ohne x zu offenbaren.
3. Bob empfängt y und tippt, ob x gerade oder ungerade war.
(Wenn Bob’s Tipp zutrifft, muß Alice sonst muß Bob fahren.)
4. Alice überprüft den Tipp und schickt x zur Verifikation an Bob,
der f (x) mit seinem zu Anfang erhaltenen y vergleicht.
91
Problem 11(a)
Sie brauchen drei Schlösser mit je zwei Schlüsseln. Wenn jede Person etwa nach folgendem Schema über Schlüssel zu zwei Schlössern
verfügt,
Alice PP
P
Schloss 1
PP P
PPP
Bob PP Schloss 2
PP
PP
PP
P Schloss 3
Claire können nur mindestens zwei Personen zusammen alle drei Schlösser
und damit den Tresor öffnen.
92
Problem 11(b)
Das folgende Schema stellt eine Lösung dar,
PP
Alice Q
Schloss
QPPP Q
P
QPPP
PP
Bob Q
Schloss
Q
P
Q
PPQ
Q
PPQ
QQ PQ
P Schloss
PP
Claire Q
P
Q
P
PPQ
PQ
PQ
P Schloss
Dennis
1
2
3
4
weil einer Person immer ein Schlüssel zu einem Schloß fehlt und zwei
Personen zusammen immer über mindestens einen Schlüssel zu jedem
der vier Schlösser verfügen.
Ist diese Lösung mit vier Schlössern mit je drei Schlüsseln auch minimal?
93
Bei drei Schlössern kann jede Person nur Schlüssel zu maximal zwei
Schlössern haben, macht bei vier Personen insgesamt maximal acht
Schlüssel, verteilt auf drei Schlösser:
es gibt aber kein Schloß mit nur einem Schlüssel, sonst könnten Paare
ohne den Inhaber dieses Schlüssels den Tresor nicht öffnen.
Also gibt es entweder eine Person mit Schlüsseln für vier oder zwei
Personen mit Schlüsseln für drei Schlösser, was in beiden Fällen zum
Widerspruch führt!
Schließlich reichen bei vier Schlössern je zwei Schlüssel pro Person
offensichtlich nicht, da dann nicht sichergestellt werden kann, daß zwei
beliebige Personen zusammen über Schlüssel für alle vier Schlösser
verfügen!
94
Problem 11(c) ???
95
Problem 12(a)
96
Problem 12(b)
97
Problem 12(c)
98
Problem 12(d)
99
Problem 13(a)
Bezeichne (x, y) den Zustand des Systems mit x Litern im 4-Liter- und
y Litern im 9-Liter-Eimer. Dann sind die folgenden Zustandsübergänge
möglich.
(0, 0) → (0, 9) → (4, 5) → (0, 5) → (4, 1) → (0, 1) → (1, 0) → (1, 9) →
(4, 6)
Problem 13(b)
(0, 0) → (3, 0) → (0, 3) → (3, 3) → (1, 5) → (1, 0)
100
101
Problem 13(c)
Bezeichne (x, y, z) den Zustand des Systems mit x Litern im 8-LiterKanister, y Litern im 5-Liter- und z Liter im 3-Liter-Krug. Dann sind
die folgenden Zustandsübergänge möglich.
(8, 0, 0) → (5, 0, 3) → (5, 3, 0) → (2, 3, 3) → (2, 5, 1) → (7, 0, 1) →
(7, 1, 0) → (4, 1, 3)
102
Problem 13(d)
Das Faß soll also 9 Liter, der Eimer 6 Liter und der Krug 3 Liter
enthalten. Bezeichne (w, x, y, z) den Zustand des Systems mit w Litern
im Faß, x Litern im Eimer, y Litern im Krug und z Liter im Becher.
Dann sind die folgenden Zustandsübergänge möglich. (18, 0, 0, 0) →
(10, 8, 0, 0) → (10, 6, 0, 2) → (10, 6, 2, 0) → (7, 6, 5, 0) → (7, 6, 3, 2) →
(9, 6, 3, 0)
103
Problem 14(a)
Sei v, m, k1 and k2 das Alter von Vater, Mutter, älterem und jüngerem
Kind. Wir wissen
a) v + m + k1 + k2 = 124
b) v + m = 3(k1 + k2 )
c) m > 2k1
d) v − m = 9(k1 − k2 )
a) und b) liefern k1 +k2 = 31 und v+m = 93 sowie 2v = 93+9(k1 −k2 )
bzw. 2m = 93 − 9(k1 − k2 ). In jedem Fall ist also k1 − k2 ungerade.
Falls k1 − k2 = 1 gilt, so folgt aus k1 + k2 = 31 eben k1 = 16 und
k2 = 15 sowie m > 32. Aus v + m = 93 und v − m = 9 folgt v = 51
und m = 42 > 32. Dies ist die einzige Lösung.
Falls nämlich k1 − k2 ≥ 3 gilt, so folgt aus k1 + k2 = 31 eben k1 ≥ 17
und k2 ≤ 14 sowie m > 34. Aus v + m = 93 und v − m ≥ 27 folgt mit
v ≥ 60 und m ≤ 33 der Widerspruch.
104
Problem 14(b)
Es gilt E = 24 = 2(A − d) mit E − d = A = 24 − d, so daß 12 =
A − d = 2A − 24 und damit A = 18 folgt.
105
Problem 14(c)
Egal, ob man zuerst den Rabatt abzieht und dann Umsatzsteuer auf15
23
23
schlägt oder umgekehrt, man muß das (1 − 15 )(1 + 100
) = 45 20
= 25
fache oder 92% des Netto-Preises bezahlen.
106
Problem 14(d)
2
1
2
1
107
Problem 14(e)
F − 5 = 2(P − 6)
F − 2P = −7)
P = 14
⇒
⇒
F + 9 = 3(P − 4)
F − 3P = −21
F = 21
108
Problem 15(a)
11
18
27
Seien A, B und C die Etiketten der drei Ecken. Aus
A∗B
B+C
A+C
27
18
11
folgt etwa B − A = 7 und daher B = 17, A = 10 sowie C = 1.
Allgemein ist also nur ein System linearer Gleichungen zu lösen. Lösungen zu Problemen
Problem 15(b)
Aus (30 − a) + (7 − a) = 34 − a folgt 3 = 3a und damit a = 1.
109
Problem 15(c)
g1 + g2 + g2 = 10, g2 = 43 g1 , g3 = 34 g2 ⇒ g1 + 34 g1 + 43 43 g1 = 10 =
⇒ g1 = 3, g2 = 4, g3 = 3.
110
10
3 g1
111
Problem 15(d)
k + ` + m + n = 79 und ` + 1 = 2k und m + 1 = 2` und n + 1 = 2m
implizieren 79 = k+2k−1+2`−1+2m−1 = 3k−3+(4k−2)+(4`−2) =
7k − 7 + (8k − 4) = 15k − 11 und damit 15k = 90, also k = 6, ` = 11,
m = 21 und n = 41.
112
Problem 15(e)
Sei m bzw. e die Anzahl der Säcke des Maultiers bzw. des Esels. Aus
m + 1 = 2(e − 1) und m − 1 = e + 1 folgt m = 7 und e = 5.
Problem 16(a)
U = 2πr = πr2 = A ⇒ r = 2
113
114
Problem 16(b)
Sei ` [m] die Länge und v [m/sec] die Geschwindigkeit des Zuges. Aus
` = 7v und 330 = (18 − 7)v folgt v = 30 [m/sec] and ` = 210 [m]. Lösungen zu Problemen
115
Problem 16(c)
Der Arbeiter stelle insgesamt x Werkstücke her. Für die ersten x2
x
x
braucht er 20
Tage, für die zweiten x2 Werkstücke braucht er 60
Tage.
60
x
Also stellt er durchschnittlich x/20+x/60 = 4 = 15 Werkstücke pro
Tag her.
116
Problem 16(d)
n = d3 103 + d2 102 + d1 10 + do ist palindromisch ⇐⇒ n = do 103 +
d1 102 + d1 10 + do . Für solche n gilt 11|n = 1000do + 110d1 + do ⇐⇒
n|1001do = 11 · 91do .
Problem 16(e)
I, a man, 7 wives, 72 sacks, 73 cats, 74 kids, i.e.
P4
5
−1
1+ i=o 7i = 1+ 77−1
= 1+ 16 (823543−1) = 1+137257 = 137258
117
Problem 16(f )
4
4 3
1 3
4 = 3 4 = (1 + 3 ) 4
118
119
Problem 17(a)
Eine Katze fängt in 5 Minuten 1 Maus. Eine Katze fängt in 100 Minuten 20 Mäuse. Fünf Katzen fangen dann 100 Mäuse in 100 Minuten.
120
Problem 17(b)
Sei 6 ≤ a, b ≤ 10 für a, b ∈ N. Dann gilt
10(a−5+b−5)+(10−a)(10−b) = 10(a+b)−100+100−10(a+b)+ab = ab
121
Problem 17(c)
Ein Huhn legt ein Ei in anderthalb Tagen. Sieben Hühner legen sieben
Eier in anderthalb Tagen. Sieben Hühner legen 28 Eier in sechs Tagen.
122
Problem 17(d)
Die Sorte bezeichne zugleich das Gewicht einer Kugel dieser Sorte.
Dann gilt A = 2B, B = 3C, C = 5D ⇒ A = 2B = 6C = 30D.
123
Problem 17(e)
Wegen der beiden Primfaktor-Zerlegungen 5291 = 11 · 13 · 37 und
3913 = 7 · 13 · 43 besteht das Zwillingspäarchen aus einem 13-jährigen
Mädchen und einem 13-jährigen Jungen.
124
Problem 18(a)
Eine Katze fängt in 5 Minuten 1 Maus. Eine Katze fängt in 100 Minuten 20 Mäuse. Fünf Katzen fangen dann 100 Mäuse in 100 Minuten.
Problem 18(b)
Man darf nicht durch 0 dividieren.
125
Problem 18(c)
Sei z der Zähler und n der Nenner. Dann gilt
65n ⇒ z = 13n ⇒ nz = 13.
126
z
n
=
z+65
n+5
⇒ 5z =
127
Problem 18(d)
Die fünf Zahlen seien n, n + 1, n + 2, n + 3, n + 4 für ein n ∈ N. Dann
gilt n2 + (n + 1)2 + (n + 2)2 = (n + 3)2 + (n + 4)2√⇒ 3n2 + 6n + 5 =
2n2 + 14n + 25 ⇒ n2 − 8n − 20 = 0 ⇒ n1,2 = 4 ± 36 ⇒ n = 10. Lösungen zu Problemen
128
Problem 18(e)
Sei f der Preis der Flasche und w derjenige des Weins. Aus f + w = 9
und w = f + 8 folgt 2f + 8 = 9 oder f = 12 .
Problem 18(f )
Sei x die Fläche seines Landes. Dann gilt
47
13
60 x + 26 = x ⇒ 60 x = 26 ⇒ x = 120.
129
x
3
+
x
4
+
x
5
+ 26 = x ⇒
130
Problem 18(g)
Es gibt 8 Würste und jeder ißt 83 Würste. Egon bezahlt für seine 83
Würste 8 Euro. Also kostet eine Wurst 3 Euro. Damit bekommt Heini
für die nicht selbstgegessenen 3 − 83 = 13 Würste genau 1 Euro und
Karl bekommt für die nicht selbstgegessenen 5 − 83 = 73 Würste genau
7 Euro.
131
Problem 18(h)
1 1 1
9+6+2
17
+ + =
=
2 3 9
18
18
Also bekommt der älteste Sohn 9 Kühe, der mittlere 6 und der jüngste
Sohn 2 Kühe. Der Nachbar, die 18. Person, bekommt keine Kuh. Lösungen zu Problemen
132
Problem 19(a)
Zeit
00
25
30
50
55
diesseits
ABCD
BC
BC
BC
ABC
B
B
B
AB
Brücke
Zeit
00
AD
D
D
D
ACD
CD
CD
CD
ABCD
10
→AD→
←A←
→AC→
←A←
→AB→
65
jenseits
15
40
50
diesseits
ABCD
CD
CD
CD
ACD
A
A
A
AB
Brücke
→AB→
←A←
→CD→
←B←
→AB→
60
jenseits
AB
B
B
B
BCD
CD
CD
CD
ABCD
Der linke Plan funktioniert offensichtlich nicht. Man spart jedoch Zeit,
wenn C und D die Brücke zusammen überqueren. Sie dürfen dies allerdings nicht als erste tun, damit jemand schnelleres die Taschenlampe
zurückbringt.
133
Problem 20(a)
134
Problem 20(b)
Man lege die Münze ganz rechts auf die Münze im Schnittpunkt der
beiden Reihen.
135
Problem 20(c)
136
Problem 20(d)
Der i-te Vasall fügt dem Wägegut i seiner Goldmünzen
P30hinzu. Würden
alle in 10g Münzen bezahlen, ergäbe die Wägung 10 i=1 i = 10 30·31
=
2
150·31g Goldmünzen. Der j-te Vasall zahlt nun mit j 9g-Münzen. Das
Fehlen von genau jg Goldmünzen überführt den j-ten Vasallen. Lösungen zu Problemen
137
Problem 21(a)
Zeit
0
1
2
3
Bauern
30
3
bezahlt -27
Schmied
30
25
25
bekommen 25
Man darf nicht Soll und Ist vermischen!
Lehrling
P
5
2
behalten 2
30
30
30
30
0
Problem 21(b)
Konstruiere einen Tetraeder im Raum (!).
138
139
Problem 21(c)
7
8
1
9
3
10
5
6
4
2
140
Problem 21(d)
Vertauschen von Zeilen oder Spalten läßt die Anzahl von Flaschen
unverändert. Man kann also erreichen, daß die Zeilen und Spalten im
Bierträger nach absteigender Anzahl von Flaschen geordnet sind.
Dann muß beispielsweise die Anzahl der Zeilen mit sechs Flaschen
gerade, nämlich zwei sein, weil sonst die rechteste Spalte eine ungerade Anzahl von Flaschen, kurz ungerade Spalten enthielte. Verbleiben
noch zwei Flaschen: in einer Zeile angeordnet entstehen zwei ungerade
Spalten, sonst zwei ungerade Zeilen.
Angenommen es gibt Zeilen mit vier Flaschen, nämlich nur genau
zwei. Verbleiben noch sechs Flaschen, die ähnlich immer zu ungeraden Zeilen oder Spalten führen.
14 Flaschen lassen sich nicht in Zeilen mit zwei Flaschen unterbringen.
141
Problem 22(a)
Der vorvorletzte Faktor lautet (x−x), so daß (x−a)(x−b) . . . (x−z) =
0 folgt.
142
Problem 22(b)
Der Pfeil zeige in Blickrichtung. Dann wechseln sich horizontal wie
vertikal stets waagerechte mit senkrechten Pfeilen ab. Der Sessel kann
also nicht in die gewünschte Position/Orientierung bewegt werden.
143
Problem 22(c)
Gegenüberliegende Eckfelder haben dieselbe Farbe. Entfernen dieser
Felder führt dazu, daß sich die Anzahl schwarzer und weißer Felder
unterscheidet. Nun deckt ein Domino-Stein aber immer genau ein weißes und ein schwarzes Feld ab. Also kann das modifizierte Schachbrett
nicht vollständig mit Domino-Steinen abgedeckt werden.
Problem 22(d)
n = 10z + 5 ⇒ n2 = 100z 2 + 100z + 25 = 100z(z + 1) + 25.
144
145
Problem 23(a)
Nein, der innerste kleine Würfel mit sechs Seiten hat keine Seite, die
mit einer der Außenseiten zusammenfällt. Um allein diesen kleinen
Würfel auszuschneiden, braucht man sachon sechs Schnitte. Damit
ist sechs das Minimum.
146
Problem 23(b)
Für eine Etage braucht man k1 = 2, für zwei Etagen k2 = k1 +1+2·2 =
7 und für drei Etagen k3 = k2 + 2 + 2 · 3 = 15 Karten, allgemein also
ki = ki−1 + (i − 1) + 2i = ki−1 + 3i − 1 mit k1 = 2. Der Ansatz
ki = Ai2 + Bi + C mit k1 = 2 liefert ki = 32 i2 + 12 i, speziell also
k47 = 23 472 + 21 47 = 21 47(3 · 47 + 1) = 47 · 71 = 3337.
147
Problem 23(c)
n : n bedeute n Dublonen links gegen n andere Dublonen rechts abzuwägen. Die mögliche drei Ergebnisse sind dann n < n (links oben),
n = n und n > n (rechts oben). Verwende folgendes Verfahren: (dabei
steht k∗ für k beliebige, nT für n echte, mR für m Dublonen aus dem
noch nicht gewogenen Rest, und F für die Fälschung)
→4∗ > 4∗, davon2∗ : 2∗→2T = 2T ⇒ 2T : 2∗
|
|
→ 2T > T F ⇒ F < T
|
|
→2T > T F ⇒ F < T
4∗ : 4∗→4T = 4T, 2T : 2R
→2T = 2T, 2T : 2R →2T = 2T ⇒ 0F
|
|
→2T < T F ⇒ F > T
|
→ 2T < T F ⇒ F > T
→4 < 4
148
Problem 23(d)
Wenn man die Zahlen in absteigender
anordnet, kann die
PReihenfolge
8
größte nicht größer als 90 sein, weil i=1 i = 36,
P9
nicht größer gleich 80 sein, weil 86=i=1 i = 45 − 8 = 37,
P9
nicht größer gleich 70 sein, weil 76=i=1 i = 45 − 7 = 38,
P9
nicht größer gleich 60 sein, weil einerseits 60+ 66=i=1 i = 60+45−6 =
99 und andererseits jeder weitere zweistellige Summand zu Summen
größer als 100 führt,
P9
P9
90 sowie 50 + 12 + 1,2,56=i=1 i = 50 + 12 + 45 − 1 − 2 − 5 = 99 und
andererseits jeder weitere zweistellige Summand größer 20 zu Summen
größer als 100 führt,
P9
P9
81 sowie 40 + 12 + 1,2,46=i=1 i = 40 + 12 + 45 − 1 − 2 − 4 = 90,
P9
40 + 21 + 1,2,46=i=1 i = 40 + 21 + 45 − 1 − 2 − 4 = 99 und andererseits
jeder weitere zweistellige Summand größer 30 zu Summen größer als
100 führt,
149
P9
nicht größer gleich 30 sein, weil einerseits 30 + 36=i=1 i = 30 + 45 −
P9
3 = 72 sowie 30 + 12 + 1,2,36=i=1 i = 30 + 12 + 45 − 1 − 2 − 3 =
P9
81, 30 + 21 + 1,2,36=i=1 i = 30 + 21 + 45 − 1 − 2 − 3 = 90 und
weitere zweistellige Summanden größer als 40 ausfielen und damit
schon behandelt wurden,
P9
P9
63 sowie 20 + 13 + 1,2,36=i=1 i = 20 + 13 + 45 − 1 − 2 − 3 = 72 und
weitere zweistellige Summanden größer als 30 ausfielen und damit
schon behandelt wurden,
P9
54 und weitere zweistellige Summanden größer als 20 ausfielen und
damit schon behandelt wurden.
P9
Bleiben lauter einstellige Summanden mit Summe i=0 i = 45.
150
Problem 24(a)
Es können nicht zwei schwarze Fähnchen aufgestellt sein, weil der Gefangene, der beide schwarzen Fähnchen sieht, sofort auf sein weißes
Fähnchen geschlossen hätte.
Es kann auch nicht genau ein schwarzes Fähnchen aufgestellt sein,
weil die beiden Gefangenen, die dieses schwarze Fähnchen sehen, sofort auf ihr weißes Fähnchen geschlossen hätten.
Also kann überhaupt kein schwarzes Fähnchen aufgestellt worden sein.
Auf diese Einsicht kommen die drei Gefangenen nahezu gleichzeitig
und nennen alle Weiß als die Farbe des Fähnchens hinter ihnen. Lösungen zu Problemen
151
Problem 25(a)
Sei K, J, F , M die Anzahl der Kinder, Jugendlichen, Frauen und
Männer. Dann gilt: 2K = J, 2F = M , 3K +3F = K +J +F +M = 81
und 2·3K = 2(K +J) = F +M = 3F , also 2K = F und daher K = 9,
J = 18 = F , M = 36.
152
Problem 25(b)
VVVLLL
Nimm das zweite volle Glas und gieße seinen Inhalt in das zweite leere
Glas.
153
Problem 25(c)
=
d.h. 1 =
√
1
154
Problem 25(d)
Mit a), b) und f) gilt
Personal
Beruf
Reisende
Verdienst
Wohnort
J
Dr. J
5000Euro/Monat
M
6= Heizer
Dr. M
B
Dr. B
Ch-burg
5000 ist nicht durch 3 teilbar. Also Dr. J kein Nachbar des Schaffners,
der in (Ch.+N)/2 und nicht in N wohnt, so daß Dr. J weder in Ch.
noch in (Ch.+N)/2 wohnt. Wegen e) wohnt Dr. J in N. Also ist Dr. M
Nachbar des Schaffners. Wegen e) heißt der Schaffner J. Also heißt
der Lokführer B.
Personal
Beruf
Reisende
Verdienst
Wohnort
J
Schaffner
Dr. J
5000Euro/Monat
N
M
6= Heizer
Dr. M
B
Lokführer
Dr. B
(Ch+N)/2
Ch
155
Problem 25(e)
Die Anzahl der Eidechsen, Käfer und Würmer sei E, K und W . Es
gilt E + K + W = 12. Eidechsen haben vier und Käfer sechs Beine.
Würmer haben keine Beine. Also gilt 4E + 6K = 26, was 0, 2, 4 6=
K ∈ {0, 1, 2, 3, 4}, also K ∈ {1, 3} impliziert.
Falls K = 1, so folgt E = 5 und W = 6 = E + K, was wegen
W > E + K ausgeschlossen ist.
Falls K = 3, so folgt E = 2 und W = 7 > E + K = 5.
156
Problem 25(f )
Der Reihe nach ergeben sich folgende Berufe:
Joe
Gärtner
Hans
6= Musiker, 6= Gärtner
Chauffeur
Maler
Klaus
6= Gärtner
Musiker
Kaufmann
Friseur
157
Problem 25(g)
Wir unterstellen, daß Schwestern denselben
Nachnamen tragen.
Martin
Bettina
Pieper
Problem 26(a)
Es gibt 12 = 1 Quadrat mit Seitenlänge 8.
Es gibt 22 = 4 Quadrate mit Seitenlänge 7.
Es gibt 32 = 9 Quadrate mit Seitenlänge 6.
...
Es gibt 88 = 64 Quadrate mit der Seitenlänge 1.
P8
=
Insgesamt gibt es also i=1 i2 = n(n+1/2)(n+1)
3
n=8
12 · 17 = 204 Quadrate.
158
8·8.5·9
3
= 24 17
2 =
159
Problem 26(b)
Zum Einfärben der äußeren drei Sektoren werden
drei Farben gebraucht. Dann braucht man eine weitere Farbe für die innere Kreis-Scheibe. Vgl.
http://de.wikipedia.org/wiki/Vier-Farben-Satz
Problem 26(c)
???
160
161
Problem 27(a)
162
Problem 28(a)
Z. Zt. t = 0 startet man beide Sanduhren. Z. Zt. t = 7 dreht man
beide Sanduhren um, so daß die 11-min-Sanduhr nach weiteren 4 min,
also z. Zt. t = 11 leerläuft. Umdrehen der 7-min-Sanduhr erlaubt, die
verbleibenden 4 min abzumessen.
163
Problem 29(a)
Die Uhr geht 6min/24 = 1/4min = 15sec pro Stunde zu spät, d.h. in
24 + 20 = 44 Stunden geht sie 11 min zu spät und zeigt um 8h eben
7:49h an.
164
Problem 29(b)
Die dritte Frau kauft ein halbes Brot. Dies machte genau die Hälfte
der verbliebenen Brote aus. Also war für die dritte Frau genau ein
Brot übrig geblieben.
Die zweite Frau findet drei Brote vor, kauft davon mit anderthalb
Laiben die Hälfte und zudem einen halben Laib, so daß für die dritte
Frau eben genau ein Brot übrig bleibt.
Die erste Frau findet sieben Brote vor, kauft davon mit drei Laiben
und einem halben Laib die Hälfte und zudem einen halben Laib, so
daß für die zweite Frau eben genau drei Brote übrig bleiben.
Der Bäcker verkauft sieben Brote.
165
Problem 29(c)
Der Stempel druckt die Nummer 1 in der zweiten Sekunde, die Nummer i in der i + 1. Sekunde. Eine Viertelstunde hat 15 · 60 = 900
Sekunden. Der Stempel druckt also in der ersten Viertelstunde die
Nummern von 0 bis 899. Die Folge 0,1, . . . , 99 enthält 10+10=20
Einsen. Die Folge 100, 101, . . . , 199 enthält 120 Einsen, Alle weiteren
hundert Nummern enthalten somit 7 · 20 = 140 Einsen, insgesamt 280
Einsen.
166
Problem 30(a)
Für die Zahl n der Demonstranten gilt n mod 2 = 1, n mod 3 = 2,
. . . n mod 10 = 9. Mit dem chinesischen Restsatz gilt n = 2519, s.a.
www.arndt-bruenner.de/mathe/scripts/chinesischerRestsatz.htm Lösungen zu Problemen
167
Problem 30(b)
Sei S bzw. B die Anzahl der Schwestern bzw. Brüder.
S − 1 = B, S = 2(B − 1) ⇒ B = 3, S = 4.
168
Problem 30(c)
Sei A bzw. B das Alter der ersten bzw. zweiten Schwester. Dann gilt
A − B = 4, A3 − B 3 = 988 = (A − B)(A2 + AB + B 2 )
⇒ A2 + AB + B 2 = A2 + A(A − 4) + (A − 4)2 = 247
⇒ 3A2 − 12A − 231 = 0
⇒ A2 − 4A − 77 = 0 ⇒ A = 11, B = 7.
169
Problem 31(a)
Es gebe n Kühe, n Schweine, n Pferde und n Kaninchen. Es überleben
4
4
1
5
5 n Kühe, 5 n Schweine, 5 n Pferde und r n Kaninchen. Dann gilt 14 =
r
rn
= 9 +r , d.h. 9+5r = 14r und damit r = 1, d.h. kein Kaninchen
9
5 n+r n
5
ist verendet.
170
Problem 32(a)
Sei F der Preis der Flasche und W der Preis des Weines. Dann gilt
9 = F +W = F +(F +8) = 2F +8, d.h. 2F = 1 und damit F = 21 . Lösungen zu Problemen
171
Problem 32(b)
Jeder Sohn bekommt den Inhalt von 13 (10 + 5) = 5 Fässern Wein.
Man gieße also die Hälfte des Inhaltes eines jeden der vollen Fässer in
eines der leeren Fässer. Dann gibt es 30 halbvolle, halbleere Fässer,
von denen jeder Sohn genau zehn Fässer bekommt.
172
Problem 33(a) Die ersten drei Fermat-Zahlen
1
2
3
F (1) = 22 + 1 = 5,
F (2) = 22 + 1 = 17,
F (3) = 22 + 1 = 257
erweisen sich auch ohne Hilfsmittel als Primzahlen. Mit calc.exe,
mit www.weblearn.hs-bremen.de/risse/MAI/docs/numerik.pdf,
mit jedem Taschenrechner erweist sich auch die vierte Fermat-Zahl
4
F (4) = 22 + 1 = 65537
als Primzahl. Erst Euler16 gelang die Faktorisierung von F (5) mit
5
F (5) = 22 + 1 = 4294967297 = 641 · 6700417
Diese und erst Recht die Faktorisierung der sechsten Fermat-Zahl
6
F (6) = 22 + 1 = 18446744073709551617 = 274177 · 67280421310721
gelingt heute bequem erst mit mächtigen Werkzeugen wie Mathematica, Maple, MATLAB, MuPAD o.ä. (vgl. /risse/symbolic/)
16
173
Problem 34(a)
Es gilt nämlich
E(41) = 1681 = 412
und beispielsweise
E(42) = 1763 = 41 · 43.
Weiterführendes s.a. www.weblearn.hs-bremen.de/risse/MAI/,
www.cs.unb.ca/profs/alopez-o/math-faq/math-faq.pdf
174
Problem 35(a)
Es gilt nämlich M (11) = 2047 = 23 · 89.
Der Lucas17 -Lehmer18 -Test, s. z.B. (3.2.8 What is the current status
on Mersenne primes?) von
www.cs.unb.ca/profs/alopez-o/math-faq/math-faq.pdf testet
effizient, ob Mersenne-Zahlen prim sind oder nicht. 1999 ergab der Rekord im Rahmen des Great Internet Mersenne Prime Search, GIMPS,
daß M (6972593) – eine Zahl mit 2098960 Dezimal-Stellen – prim ist.
Jeder kann idle cycles seines PCs für die Bestimmung von primen
Mersenne-Zahlen zur Verfügung stellen, s.
Great Internet Mersenne Prime Search (GIMPS)
GIMPS betreibt übrigens viele weitere Projekte des distributed computing.
17 François
18 Derrick
E.A. Lucas (1842-1891)
www-history.mcs.st-and.ac.uk/Biographies/Lucas.html
N. Lehmer (1867-1938) www.math.berkeley.edu/publications/newsletter/2000/lehmer.html
175
Problem 36(a)
Den (n mod 7)-ten Wochentag, wobei die Wochentage zyklisch anzuordnen sind, numeriert von 0 bis 6, beginnend mit dem heutigen
Wochentag.
176
Problem 36(b)
Den (7 − (n mod 7)) mod 7-ten Wochentag, wobei die Wochentage
zyklisch anzuordnen sind, numeriert von 0 bis 6, beginnend mit dem
heutigen Wochentag.
177
Problem 36(c)
siehe etwa
www.cl.cam.ac.uk/~mgk25/iso-time.html
178
Problem 37(a)
Per Definition gilt für m, n, r ∈ N
n mod m = r ⇐⇒ n = v · m + r für ein v ∈ N
⇐⇒ n − r = v · m für ein v ∈ N
⇐⇒ m|n − r ⇐⇒ n ≡ r (mod m)
179
Problem 37(b)
Additivität:
n1 ≡
r1 (mod m) ⇒
n1 − r1 = v1 m
n2 ≡
r2 (mod m) ⇒
n2 − r2 = v2 m
(n1 ± n2 ) ≡ (r1 ± r2 ) (mod m) ⇐ n1 + n2 − (r1 + r2 ) = (v1 + v2 )m
Multiplikativität:
m|n1 − r1
m|r2 (n1 − r1 )
ni ≡ ri (mod m) ⇒
⇒
⇒
m|n2 − r2
m|n1 (n2 − r2 )
m|r2 (n1 − r1 ) + n1 (n2 − r2 ) = n1 n2 − n1 r2 + n1 r2 − r1 r2
⇒ n1 · n2 ≡ r1 · r2 (mod m)
180
Problem 37(c)
skalare Vielfache
n ≡ r (mod m) ⇒ m|n − r ⇒ m|c(n − r) ⇒ c · n ≡ c · r (mod m)
Potenzen entweder per Multiplikativität
oder direkt etwa durch voll√
ständige Induktion: p=1
bleibt also nur np ≡ rp(mod m) ⇒ np+1 ≡ rp+1(mod m) zu zeigen
n ≡ r (mod m)
m|n − r
m|rp (n − r)
⇒
⇒
⇒
np ≡ rp (mod m)
m|np − rp
m|n(np − rp )
m|rp (n − r) + n(np − rp ) = np+1 − nrp + nrp − rp+1
⇒ np+1 ≡ rp+1 (mod m)
181
Problem 37(d)
Transitivität
r ≡ s (mod m), s ≡ t (mod m) ⇒ m | r − s, m | s − t
⇒ m | (r − s) + (s − t) = r − t ⇒ r ≡ t (mod m)
182
Problem 38(a)
Division durch 3: (wegen Potenzieren)
10o = 1 ≡ 1 (mod 3) ⇒ 10p ≡ 1 (mod 3)
und (wegen Multiplikativität)
zi 10i = zi ≡ 1 (mod 3) ⇒ n =
∞
X
i=0
zi 10i ≡
∞
X
zi (mod 3)
i=0
Speziell gilt also
s(n) ≡ 0 (mod 3) ⇒ n ≡ 0 (mod 3)
Division durch 9: analog! z.B.
1234567890 mod 3 = (1 + 2 + . . . + 9) mod 3 = 45 mod 3 = 0
1234567890 mod 9 = (1 + 2 + . . . + 9) mod 9 = 45 mod 9 = 0
Die üblichen Tests für Teilbarkeit durch 2,4 oder 5 können entsprechend hergeleitet werden.
183
Problem 38(b)
Divisionsreste modulo 11 der Zehner-Potenzen:
2i
10 ≡ 1 (mod 11)
10o ≡ 1 (mod 11)
⇒
102i+1 ≡ 10 (mod 11) ≡ −1 (mod 11)
101 ≡ 10 (mod 11)
Damit folgt per Arithmetik modulo 11
z2i 102i ≡ z2i (mod 11) und z2i+1 102i+1 ≡ −z2i+1 (mod 11)
Zusammen mit der Transitivität ergibt sich ein Test auf Teilbarkeit
durch 11:
11 |
∞
X
i=o
i
(−1) zi ⇒ 11 |
∞
X
zi 10i
i=0
und z.B.
1234567890 mod 11 = (−1 + 2 − 3 + 4 − 5 + 6 − 7 + 8 − 9 + 0) mod 11 =
−5 mod 11 = 6
184
Problem 38(c)
Einige Beispiele mögen das Verfahren illustrieren:
Prüfziffer der ISBNummer 1-86197-222 ist 1-86197-222-9, da
1·1+2·8+3·6+4·1+5·9+6·7+7·2+8·2+9·2 = 174 mod 11 = 9 mod 11
1·3+2·9+3·3+4·3+5·1+6·4+7·6+8·6+9·7 = 48 mod 11 = 4 mod 11
1·3+2·9+3·3+4·3+5·1+6·4+7·6+8·4+9·3 = 51 mod 11 = 7 mod 11
Prüfziffer der ISBNummer 0-550-10206 ist 0-550-10206-X, da
1·0+2·5+3·5+4·0+5·1+6·0+7·2+8·0+9·6 = 32 mod 11 = 10 mod 11
185
Problem 38(d) Divisionsreste
modulo 7 der Zehner-Potenzen:

 7i+0
10o ≡ 1(mod 7)
10
≡ 1(mod 7) ≡ −6(mod 7)





7i+1

101 ≡ 3(mod 7)
≡ 3(mod 7) ≡ −4(mod 7)
10







102 ≡ 2(mod 7)

107i+2 ≡ 2(mod 7) ≡ −5(mod 7)
103 ≡ 6(mod 7) ⇒ 107i+3 ≡ 6(mod 7) ≡ −1(mod 7)



104 ≡ 4(mod 7)
107i+4 ≡ 4(mod 7) ≡ −3(mod 7)






5


10 ≡ 5(mod 7)
107i+5 ≡ 5(mod 7) ≡ −2(mod 7)




 7i+6
6
10 ≡ 1(mod 7)
≡ 1(mod 7) ≡ −6(mod 7)
10
P∞
Damit gilt für n = i=0 zi 10i per Arithmetik modulo 7
n≡
∞
X
z7i+0 +3z7i+1 +2z7i+2 −z7i+3 −3z7i+4 −2z7i+5 +z7i+6
(mod 7)
i=0
Die Transitivität liefert nun einen Test auf Teilbarkeit durch 7:
P∞
7| i=0 z7i+0P+ 3z7i+1 + 2z7i+2 − z7i+3 − 3z7i+4 − 2z7i+5 + z7i+6
∞
⇒ 7 | i=0 zi 10i
und z.B. 1234567890 mod 7 = (2·1+3·2+1·3+1·4−2·5−3·6−1·7+
2·8+3·9+1·0) mod 7 = (2+6+3+4−10−18−7+16+27) mod 7 =
23 mod 7 = 2
186
Problem 38(e) Parität, parity bzw. Error Correcting Codes, ECC
sind Beispiele Fehler-erkennender oder sogar Fehler-korrigierender Codierungen von Informationen. Sie sichern Daten gegen Verfälschung
bei Übertragung (LAN, wLAN, Satellit, ...) oder Speicherung (HD,
RAID, CD-ROM, DVD ...).
z.B. Das Paritätsbit bo für odd/even parity ist so zu setzen, daß die
Anzahl der gesetzten bits in einem bit-String b1 . . . bn inclusive
parity bit bo ungerade/gerade ist. Mit einem Paritätsbit werden
1-bit Fehler erkannt.
n
X
1 mod 2 für odd parity
bi =
0 mod 2 für even parity
i=o
Übrigens, odd parity ist Standard19 für synchrone, even parity
für asynchrone Übertragung.
z.B. Selbstverständlich ist es aufwändiger, Fehler zu korrigieren als
nur ihr Vorhandensein festzustellen. Entsprechend komplexer
sind die Algorithmen, wie z.B. CRC oder Reed-Solomon-Codes.
19 s.
z.B. www.its.bldrdoc.gov/projects/t1glossary2000/ parity check.html
187
Erläuterung einschlägiger Verfahren zur Fehler-Korrektur bieten etwa
Cyclic Redundancy Codes, CRC, s.
ftp.informatik.uni-trier.de/pub/Users-CTVD/sack/ep/CRC.txt
20
Reed -Solomon20 -Code, s. www.4i2i.com/reed solomon codes.htm,
www.cs.cornell.edu/Courses/cs722/2000sp/ReedSolomon.pdf
...
20 Irving Reed (1923-?), Gustave Solomon (1931-1996)
hotwired.lycos.com/synapse/feature/97/29/silberman2a 1.html
188
Problem 39(a)
Sei a < b (sonst ist nichts zu tun).
Sei b = va + r mit r = b mod a.
Falls r = 0, so ist ggT(a, b) = a wie auch ggT(a, (va) mod a) =
ggT(a, 0) = a.
Falls r > 0, so gilt für d = ggT(a, r) eben d | a und d | r und damit
auch d | b = va + r.
Bleibt zu zeigen, daß d auch größter Teiler von a und b ist.
Für ein d0 ∈ N mit d0 | a und d0 | b = va + r folgt d0 | r. Da ja
d = ggT(a, r), gilt d0 | d.
Insgesamt ist also ggT(a, r) = d = ggT(a, b).
189
Problem 39(b) Rekursive Version des Euklid’schen Algorithmus’
ggT(a,b)
{
if (b==0) return a; else return ggT(b,a mod b);
}
Der Algorithmus terminiert, weil bei jedem Rekursionsschritt die Argumente abwechselnd um mindestens 1 dekrementiert werden.
ggT(
,
)
=
Iterative Version des Euklid’schen Algorithmus’
ggT(a,b)
{
while (b != 0) { tmp=b; b=a mod b; a=tmp; } return a;
}
ggT(
,
)
=
190
Problem 39(c)
Beweis des FLT nach [25] S.54-55
Für primes p ist G = (Z/pZ)∗ = {1, 2, . . . , p − 1} eine multiplikative Gruppe mit p − 1 Elementen (abgeschlossen unter Multiplikation modulo p mit Eins-Element 1), also eine Gruppe der Ordnung
ord(G) = p − 1.
Jedes x ∈ G erzeugt nun eine Untergruppe < x >= {x1 , x2 , . . .} in
G ⊃< x >. Da sich G als disjunkte Vereinigung etwa der Linksnebenklassen g < x > (mit identischer Kardinalität |g < x > | für alle g ∈ G)
darstellen läßt, gilt – wie für jede Untergruppe H einer Gruppe G –
ord(x) = ord(< x >) | ord(G)
Für a ∈ G, d.h. für zu p teilerfremde a, gilt v · ord(a) = ord(G) und
damit
ap−1 = aord(G) = av·ord(a) = (aord(<a>) )v = 1v = 1
oder eben die Aussage des kleinen Satzes von Fermat
ap−1 ≡ 1
(mod p)
191
z.B. m = 11111 ist nicht prim, da 211110 ≡ 10536 (mod 11111), denn
215 ≡ 10546 (mod m),
290 ≡ 105466 (mod m) ≡ 7830 (mod m)
2150 ≡ 1054610 (mod m) ≡ 3771 (mod m), 2310 ≡ 10536 (mod m)
2540 ≡ 78306 (mod m) ≡ 1 (mod m), 210800 = (2540 )20 ≡ 1 (mod m)
Ebenso ist m = 11111 nicht prim, da 311110 ≡ 2410 (mod 11111), denn
39 ≡ 19683 (mod m) ≡ 8572 (mod m),
310 ≡ 3494 (mod m)
360 ≡ 34946 (mod m) ≡ 9757 (mod m),
370 ≡ 2410 (mod m)
3120 ≡ 97572 (mod m) ≡ 1 (mod m), 311040 = (3120 )92 ≡ 1 (mod m)
ˆ
ˆ
=
≈21
(mod 11111 )
21
eben im Rahmen der Darstellungsgenauigkeit
192
Problem 39(d)
Die Implikation ist äquivalent zu FLT mit p = n und a = 2.
FLT: 2n−1 ≡ 1 (mod n) ⇒ 2n−1 − 1 ≡ 0 (mod n) ⇒ n|2n−1 − 1.
Sei dagegen n = 341. Wegen 341 = 11 · 31 ist n zusammengesetzt, also
nicht prim. Es gilt aber dennoch 2340 ≡ 1 (mod 341), denn
210 = 3·341+1 ⇒ 210 −1 = 3·341 ⇒ 341|210 −1 ⇒ 210 ≡ 1 (mod 341)
Das Gegenbeispiel ergibt sich nun durch Potenzieren:
2340 ≡ 1 (mod 341) ⇒ 341|2340 − 1
z.B. 341 ist zusammengesetzt, da 3340 ≡ 56(mod 341). Denn
36 = 47 mod 341, 37 = 141 mod 341, 38 = 82 mod 341
39 = 246 mod 341, 310 = 56 mod 341, 330 = 1 mod 341
3330 = 1 mod 341, zusammen also 3340 = 56 mod 341
193
Problem 40(a)
Wenn |M | die Kardinalität der Menge M , also die Anzahl der Elemente von M bezeichnet, ist offensichtlich
ϕ(p) = |{m ∈ N : m < p, ggT(m, p) = 1}| = |{1, 2, . . . , p − 1}| = p − 1
Im Übrigen ist ϕ(n) für kleine n schnell bestimmt:
n
ϕ(n)
2
3
4
5
6
7
8
9
10
1
2
2
4
2
6
4
6
4
n
11
12
13
14
15
16
17
18
19
20
ϕ(n)
10
4
12
6
8
8
16
6
18
8
n
21
22
23
24
25
26
27
28
29
30
ϕ(n)
12
10
22
8
20
12
18
12
28
8
194
Problem 40(b)
Zu zeigen ist, daß es pk−1 − 1 verschiedene m < pk gibt, die gemeinsame Teiler mit pk , d.h. die (u.a.) den Teiler p haben.
|{m = vp : m = vp < pk }| = |{m = vp : 1 ≤ v < pk−1 }| = pk−1 − 1
Also ist
ϕ(pk )
= |{1, 2, . . . , pk − 1} \ {m = vp : 1 ≤ v < pk−1 }|
= |{1, 2, . . . , pk − 1}| − |{m = vp : 1 ≤ v < pk−1 }|
= pk − 1 − (pk−1 − 1) = pk − pk−1
Problem 40(c)
195
Sei n = r · s mit teilerfremden Faktoren r und s.
Die Menge M = {m ∈ N : m < n, ggT(m, n) = 1} läßt sich wie folgt
aufzählen: Jedes zu r teilerfremde r0 und jedes zu s teilerfremde s0
liefert ein zu n teilerfremdes m = r0 · s0 , d.h.
{r0 < r : ggT(0 r, r) = 1} × {s0 < s : ggT(0 s, s) = 1} ⊂ M
Umgekehrt ist jeder Teiler von m ∈ M entweder Teiler von r oder
von s. Seine Primfaktorzerlegung läßt sich also als Produkt von zwei
Faktoren auffassen, die teilerfremd entweder zu r oder zu s sind.
ϕ(n)
=
|M |
=
|{r0 < r : ggT(0 r, r) = 1} × {s0 < s : ggT(0 s, s) = 1}|
=
|{r0 < r : ggT(0 r, r) = 1}| · |{s0 < s : ggT(0 s, s) = 1}|
=
ϕ(r) · ϕ(s)
196
Problem 40(d)
Jedes n ∈ N hat eine Primfaktorzerlegung
v
Y
n=
pvi i
i=1
wobei vi die Vielfachheit des Primfaktors pi und v die Anzahl der
Primfaktoren bezeichnen. Damit gilt
v
v
Y
Y
vi
vi −1
ϕ(n) =
pi − pi
=n
1 − 1/pi
i=1
i=1
aber eben nur, wenn die Primfaktorzerlegung von n überhaupt bekannt ist.
Für prime p und q sowie n = p · q gilt also insbesondere
ϕ(n) = ϕ(p·q) = ϕ(q)·ϕ(q) = (p−1)(q−1) = p·q−p−q+1 = n−(p+q)+1
Problem 40(e)
197
Beweis nach [25] S.57
Sei wie im Beweis des kleinen Satzes von Fermat G = (Z/nZ)∗ , d.h.
die Gruppe der invertierbaren Elemente von Z/nZ mit dem Einselement [1] ∈ Z/nZ. G besteht also gerade aus den Elementen [m] ∈
Z/nZ, deren Repräsentanten m ein modulo-n Inverses haben. Dies
sind genau die Elemente [m] mit zu n teilerfremden Repräsentanten
m. Also ist G = {[m] : 1 ≤ m < n, ggT(m, n) = 1} und damit
ord(G) = ϕ(n).
Mit ggT(a, n) = 1 ist also [a] ∈ G und damit aord(G) = [1] oder eben
aϕ(n) = aord(G) ≡ 1 (mod n)
198
Problem 41(a)
Aus ggT(mi , mj ) = 1, folgt ggT(bi , mi ) = 1 für i = 1, . . . , n.
Daher existiert das (modulo mi )-Inverse xi zu bi , d.h.
xi bi ≡ 1 (mod mi )
für i = 1, . . . , n
Zudem ist bi xi ≡ 0 (mod mj ) falls i 6= j, also xi bi ≡ δij (mod mi ).
Mit
n
X
x=
xi bi ri
i=1
gilt also für j = 1, . . . , n
n
X
x mod mj =
(xi bi ri ) mod mj = (xj bj rj ) mod mj = rj
i=1
199
Problem 41(b)
Offensichtlich gilt
x = y mod p ⇐⇒ x − y ∈ pZ ⇐⇒ p | (x − y)
x = y mod q ⇐⇒ x − y ∈ qZ ⇐⇒ q | (x − y)
Da nach Voraussetzung p und q teilerfremd sind, folgt
(pq) | (x − y) ⇐⇒ x − y ∈ (pq)Z ⇐⇒ x = y mod (pq)
200
Problem 41(c) Sei a das zu bestimmende Alter. Erfragt werden
r1 = a%3,
a = r1 mod 3,
a ≡ r1
(mod 3)
r2 = a%5,
a = r2 mod 5,
a ≡ r2
(mod 5)
r3 = a%7, a = r3 mod 7, a ≡ r3 (mod 7)
Q3
Dann gilt m = 1 mi = 3 · 5 · 7 = 105. Weiterhin ist b1 = 105/3 = 35,
b2 = 105/5 = 21 und b3 = 105/7 = 15. Die (modulo mi )-Inversen sind
x1 = 2 wegen 2 · 35 = x1 b1 = 1 mod m1 = 1 mod 3,
x2 = 1 wegen 1 · 21 = x2 b2 = 1 mod m2 = 1 mod 5 und
x3 = 1 wegen 1 · 15 = x3 b3 = 1 mod m3 = 1 mod 7.
Damit gilt
a=
3
X
xi bi ri mod m = (70 r1 + 21 r2 + 15 r3 ) mod 105
1
201
Problem 42(a) Verwende einerseits a+0 = 0+a = a und andererseits
a · 1 = 1 · a = a, um bis auf eines alle Ergebnisse in der Additionsbzw. in der Multiplikationstabelle zu bestimmen.
+ 0
0 0
1 1
1
1
0
·
0
1
0
0
0
1
0
1
Definierte man 1 + 1 = 1, dann hätte 1 kein inverses Element bzgl.
der Addition.
Definierte man 1 · 1 = 0, dann hätte 1 kein inverses Element bzgl. der
Multiplikation.
Addition läßt sich also als XOR oder als Addition modulo 2 interpretieren und implementieren. Multiplikation läßt sich also als AND oder
als Multiplikation modulo 2 interpretieren und implementieren.
202
Problem 42(b) Kommutative Addition und Multiplikation in GF(3)
+
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
·
0
1
2
0
0
0
0
1
0
1
2
2
0
2
1
203
Problem 42(c) Kommutative Addition und Multiplikation in GF(5)
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
·
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
204
Problem 42(d) Für jedes prime p machen jeweils die Addition
modulo p aus GF(p) und die Multiplikation modulo p aus GF(p)∗
kommutative Gruppen – mit Distributivität.
a=
b=
a+b=
a·b=
m= 6
eval
reset
Für p, q ∈ GF(pq)∗ würde jedoch unzulässigerweise p · q = 0 gelten, so
daß das Produkt von Null verschiedener Faktoren verschwände.
205
Pn−1
Problem 43(a) Für r(x) = i=0 ri xi ∈ GF(pn ) und s(x) =
GF(pn ) mit ri , si ∈ GF(p) definiert man
(r + s)(x) :=
n−1
X
Pn−1
i=0
si xi ∈
(ri + si )xi ∈ GF(pn )
i=0
GF(pn ), + ist dann offensichtlich eine kommutative (additive) Gruppe. Deren Null-Element ist das konstante Polynom null(x) = 0xo . Das
Pn−1
Inverse eines Polynoms q(x) = i=0 ci xi ∈ GF(pn ) bzgl. dieser AdPn−1
dition ist das Polynom −q(x) = i=0 (p − ci mod p)xi ∈ GF(pn ).
r = 1,0,1,0
s = 1,1,0,1,1
r=
s=
r+s=
p= 2
n= 8
add
s := −r
reset
206
Problem 43(b)
Pn−1
Pn−1
Seien r(x) = i=0 ri xi ∈ GF(pn ) und s(x) = i=0 si xi ∈ GF(pn )
mit ri , si ∈ GF(p). Dann gilt
2n−2
i
X X
rs (x) :=
xi
rj si−j ∈ P(2n − 1)
i=0
j=0
Weil offensichtlich i.a.R. r · s ∈ P(2n − 1) gilt, liegt das Produkt von
Faktoren in GF(pn ) nicht notwendig wieder in GF(pn ).
207
Problem 43(c) Dann muß das Polynom m den Grad n haben. Ein
Polynom m mit kleinerem Grad leistet nicht das Gewünschte, wie
folgendes Beispiel für GF(22 ) zeigt.
m(x) = x
0
1
∗
0
0
0
1
0
1
0
x
x
x+1 0 x+1
x
0
x
0
0
x+1
0
x+1
0
1
m(x) = x + 1
∗
0
1
0
0
0
1
0
1
0
x
x
x+1 0 x+1
x
0
x
1
0
x+1
0
x+1
0
0
In beiden Fällen ergeben sich Widersprüche. Für m(x) = x hat beispielsweise x kein Inverses. Für m(x) = x + 1 hat beispielsweise x + 1
kein Inverses.
208
Problem 43(d) Dann muß m irreduzibel sein, d.h. m kann nicht als
Produkt zweier nicht-konstanter Polynome niedrigeren Grades dargestellt werden. Denn angenommen, m = m1 · m2 mit nicht-konstanten
Polynomen m1 und m2 , deren Grad nicht größer als n ist. Dann gälte
m1 , m2 ∈ GF(pn ) und damit zwangsläufig m1 · m2 = 0 in GF(pn ). Lösungen zu Problemen
209
Problem 43(e) Wegen m1 (x) = x2 + 1 = x2 + 2x + 1 = (x + 1)2 ist
m1 reduzibel über GF(2). Auflisten aller geeigneten Produkte zeigt,
daß m2 = x2 + x + 1 über GF(2) irreduzibel ist.
x·x
x · (x + 1)
(x + 1) · x
(x + 1) · (x + 1)
=
=
=
=
x2
x2 + x
x2 + x
x2 + 2x + 1 = x2 + 1
210
Problem 44(a) Multiplikation in GF(22 ) = GF(2)[x]/m(x) mit m(x) =
x2 + x + 1 ist durch die folgende Tabelle gegeben
·
0
1
x
x+1
0
0
0
0
0
1
0
1
x
x+1
x
0
x
x+1
1
x+1
0
x+1
1
x
weil
x2 = x + 1 mod m(x)
und
x(x + 1) = x2 + x = x + 1 + x = 1 mod m(x)
und
(x + 1)2 = x2 + 2x + 1 = x2 + 1 = x + 2 = x mod m(x).
Die inversen Elemente können direkt aus der Multiplikationstabelle
ausgelesen werden.
211
Pn−1
i
n ∗
Problem 44(b) Für r(x) =
i=0 ri x ∈ GF(p ) und s(x) =
Pn−1
i
n ∗
i=0 si x ∈ GF(p ) mit ri , si ∈ GF(p) definiert man


n−1
i
X X
(r · s)(x) := 
xi
rj si−j  mod m(x) ∈ GF(pn )
i=0
j=0
n ∗
Dann ist GF(p ) , · eine kommutative (multiplikative) Gruppe. Deren Eins-Element ist das konstante Polynom eins(x) = 1xo .
m = 1,0,0,0,1,1,0,1,1
r = 1,0,1,0,1
s = 1,1,0,1,1
m=
r=
s=
r·s =
g=
next irr poly
p= 2
n= 8
irreduzibel?
multipliziere
s := 1/r
reset
|{irr poly}|
next generator
212
Problem 44(c) Mit der erweiterten Version des Euklid’schen Algorithmus auf S. 40.
Zunächst sei also der klassische Algorithmus in rekursiver und iterativer Form präsentiert, der ggT(x, y) = gcd(x, y) berechnet.
gcd rec(int x,y)
{
if (y=0)
return abs(x);
else
return gcd rec(y,mod(x,y));
}
gcd it(int x,y)
{ int tmp;
while (y<>0) {
tmp = y; y = mod(x,y);
x = tmp; }
return abs(x)
}
Der erweiterte Euklid’sche Algorithmus berechnet zu gegebenen x und
y nun Koeffizienten a und b, so daß d = ggT(x, y) = ax + by gilt.
Mit primem p und 0 ≤ x < p gilt dann 1 = ggT(x, p) = ax + bp,
d.h. ax = 1 − bp oder eben ax = 1 mod p. Der erweiterte Euklid’sche
Algorithmus invertiert also in GF(p) und analog in GF(pn ).
gcd coeff(int x,y) % returns vector
{
int q,tmp,q11,q12,q22,t21,t22;
q11 = q22 = 1;
q12 = q21 = 0;
while (y<>0)
{
tmp = y;
q = x / y;
y = x % y;
x = tmp;
t21 = q21; t22 = q22;
q21 = q11 - q*q21;
q22 = q12 - q*q22;
q11 = t21; q12 = t22;
}
return vector(x,q11,q12);
}
213
214
Problem 44(d) Mithilfe der Möglichkeit im Formular auf S. 211,
irreduzible Polynome über GF(p) von gegebenem Grad n zu erzeugen,
kann folgende kleine Tabelle aufgestellt werden:
p\
n
2
2
1
3
6
5 40
..
. ...
3
2
16
160
4
5
3
6
36 96
600 . . .
6
7
8
9 18 30
232 . . .
...
...
Übrigens, man kann zeigen, daß es immer mindestens ein irreduzibles
Polynom über GF(p) vom Grad n gibt.
215
Problem 44(e) Seien m1 (x) und m2 (x) zwei irreduzible Polynome
über GF(p) vom Grad n−1 und Fi der mit mi (x) konstruierte Körper.
Diese beiden Körper sind isomorph, d.h. bis auf Umbenennung ihrer
Elemente identisch, d.h. es gibt einen Isomorphismus, also eine bijektive Abbildung ϕ : F1 → F2 mit ϕ(r + s) = ϕ(r) + ϕ(s) und
ϕ(r · s) = ϕ(r) · ϕ(s)
• weil zwei endlich Körper mit gleich vielen Elementen isomorph
sind
• oder weil endliche Körper zyklisch sind, d.h. daß es für jeden
endlichen Körper F ein erzeugendes Element g mit F∗ = {g i ; i ∈
N} gibt. Sei also gi erzeugendes Element von Fi . Dann stellt
die Abbildung ϕ : F1 → F2 definiert durch ϕ(g1 ) := g2 und
kanonisch auf ganz F1 fortgesetzt einen Isomorphismus zwischen
F1 und F2 dar.
216
Problem 44(f ) Offensichtlich hat GF(22 )∗ mit m(x) = x2 + x + 1
genau zwei erzeugende Elemente, nämlich g1 (x) = x und g2 (x) = x+1.
n
0
1
2
g1n = xn
g10 = 1
g11 = x
g12 = x + 1
n
0
1
2
g2n = (x + 1)n
g20 = 1
g21 = x + 1
g22 = x
GF(23 )∗ mit m(x) = x3 + x + 1 hat mindestens drei erzeugende Elemente: x, x + 1 und x2 .
n
0
1
2
3
4
5
6
xn
1
x
x2
x+1
x2 + x
x2 + x + 1
x2 + 1
n
0
1
2
3
4
5
6
(x + 1)n
1
x+1
x2 + 1
x2
x2 + x + 1
x
x2 + x
n
0
1
2
3
4
5
6
(x2 )n
1
x2
x2 + x
x2 + 1
x
x+1
x2 + x + 1
GF(23 )∗ mit m(x) = x3 + x2 + 1 hat mindestens drei erzeugende
217
Elemente: x, x + 1 und x2 .
n
0
1
2
3
4
5
6
xn
1
x
x2
x2 + 1
x2 + x + 1
x+1
x2 + x
n
0
1
2
3
4
5
6
(x + 1)n
1
x+1
x2 + 1
x
x2 + x
x2 + x + 1
x2
n
0
1
2
3
4
5
6
(x2 )n
1
x2
x2 + x + 1
x2 + x
x
x2 + 1
x+1
Das ist nicht überraschend: aufgrund der Isomorphie ist die Menge
der erzeugenden Elemente unabhängig von der Wahl des irreduziblen
Polynoms m.
Es gibt weitere erzeugende Elemente von GF(23 )∗ : das Formular auf
S. 211 berechnet nämlich schrittweise alle erzeugenden Elemente von
GF(pn )∗ für jedes (kleine) prime p und (kleine) n ∈ N.
218
Problem 44(g) Sei g ein erzeugendes Element von GF(pn )∗ und sei
log r der Logarithmus von Elementen r ∈ GF(pn )∗ zur Basis g. Dann
kann die Multiplikation auf eine Addition und drei table look ups
reduziert werden:
(r · s) = g log r+log s
Betrachte beispielsweise GF(28 )∗ . Dann sind statt einer look up Tabelle mit 256·256 = 65536 Einträgen für die Multiplikation in GF(28 )∗
nur zwei look up Tabellen mit je 256 Einträgen nötig.
219
Problem 44(h) Wegen
1/r = r−1 = g − log r = g p
n
−1−log r
kann die Invertierung in GF(pn )∗ durch zwei table look ups und eine
Subtraktion implementiert werden.
220
Problem 45(a)
Mit k = 3 ergibt sich folgender Klar-Text
thisisatopsecretmessage.
Offensichtlich gibt es genau 26 mögliche Schlüssel.
Die Caesar-Verschlüsselung erhält also u.a. die Buchstabenhäufigkeiten der verwendeten Sprache! – ein Schwäche, die Angriffe ausnutzen
können.
s.a. www.weblearn.hs-bremen.de/risse/MAI/docs/mai1.pdf
k=C
Caesar
Caesar−1
x=
y=
x=
B
? Besonderheiten der Implementierung ?
221
Problem 45(b)
Außer dem trivialen Schlüssel 0 gibt es nur 25 ’richtige’ Schlüssel
k = 1, 2, . . . , 25 im Schlüsselraum {0, 1, 2, . . . , 25}.
Die Sicherheit der Caesar-Verschlüsselung ist sehr niedrig, da ja nur
diese 25 Schlüssel ausprobiert werden müssen.
222
Problem 46(a)
Ohne Beschränkung der Allgemeinheit sei k = k mod m .
Die Verschlüsselung muß umkehrbar-eindeutig sein, d.h.
(k x1 ) mod m = (k x2 ) mod m ⇒ x1 = x2
für alle 0 ≤ x1 , x2 < m
oder ebenso
x1 6= x2 ⇒ (k x1 ) mod m 6= (k x2 ) mod m
für alle 0 ≤ x1 , x2 < m
Dann sind notwendigerweise k und m teilerfremd. Denn sonst existiert
ein g ∈ N mit k = v g und m = w g. Für 0 = x1 6= x2 = w < m gilt
dann
(k x1 ) mod m = 0 mod m = 0 = (v w g) mod (w g)
223
Problem 46(b) Wenn 1 = (k k inv ) mod m, genau dann gilt
x = (k inv y) mod m = (k inv ((k x) mod m)) mod m = (k inv k x) mod m
für jedes 0 ≤ x < m. Dann heißt k inv das (modulo-m)-Inverse zu k.
Der Euklid’sche Algorithmus ggT(xo , x1 ) berechnet für teilerfremde
xo und x1 (bis auf Vertauschung der Argumente)
xo = q1 x1 + x2
x1 = q2 x2 + x3
x2 = q3 x3 + x4
x2 = xo − q1 x1
x3 = x1 − q2 x2 = x1 − q2 (xo − q1 x1 )
x4 = x2 − q3 x3 = xo − q1 x1 −q3 (x1 −q2 (xo −q1 x1 ))
..
.
xn−2 = qn−1 xn−1 + xn
xn−1 = qn xn + xn+1
xn = Linearkombination von xo und x1
bis xn = 1 und xn+1 = 0. Jedes xi ist also als Linearkombination
von xo und x1 darstellbar. Insbesondere gilt also für ggT(k, m) eben
xn = 1 = u k + v m falls ggT(k, m) = 1. Damit folgt
u k = 1 − vm ⇒ (u k) = 1 mod m
u ist also das (modulo m)-Inverse k inv zu k.
224
Der Euklid’sche Algorithmus wird nun erweitert, um das modulo-m
Inverse von k zu berechnen
function invers(k,m)
{
var xm=m,x=k,xp,q;
var l11=1, l12=0, l21=0, l22=1, n11, n12, n21, n22;
while (xm != 1)
{
q=Math.floor(xm/x); xp=xm-x*q;
n11=l21; n12=l22; n21=l11-q*l21; n22=l12-q*l22;
l11=n11; l12=n12; l21=n21; l22=n22; xm=x; x=xp;
}
return (l12+m)-m*Math.floor((l12+m)/m);
}
k=
m=
(modulo m)
-Inverse zu k
k inv =
225
Problem 46(c)
Einsetzen liefert
x =
=
(k10 y + ko0 ) mod m = (k10 ((k1 x + ko ) mod m) + ko0 ) mod m
(k10 k1 x + k10 ko + ko0 ) mod m = x
genau dann, wenn
k10 = k1inv
und
ko0 = (−k1inv ko ) mod m
Selbstverständlich gilt dann auch
y
=
(k1 x + ko ) mod m = (k1 ((k1inv y + ko0 ) mod m) + ko ) mod m
=
(k1 k1inv y + k1 ko0 + ko ) mod m
=
(y + k1 (−k1inv ko ) + ko ) mod m = y
226
Problem 46(d)
Jeder Schlüssel besteht aus einem Paar (k1 , ko ) mit ko ∈ {0, 1, . . . , m−
1} und k1 ∈ {0 ≤ k < m : ggT(k, m) = 1}. Der Schlüsselraum ist
{1, 2, . . . , 25} × {0 ≤ k < m : ggT(k, m) = 1}.
Beispielsweise für m = 26 hat der Schlüsselraum 26 · ϕ(26) = 26 · 12
Elemente.
Dennoch ist die Sicherheit der allgemeinen Caesar-Verschlüsselung
(unverändert) niedrig, da u.a. die Buchstabenhäufigkeiten weiterhin
erhalten bleiben.
227
Problem 47(a)
Mit Schlüsselwort key oder eben k = 10, 4, 24, d.h. l = 3 ergibt sich
folgender Klar-Text
thisisatopsecretmessage.
Offensichtlich gibt es genau 26l mögliche Schlüssel der Länge l. Die
Perioden-Länge l kann mit dem Verfahren von Kasiski ermittelt werden. Dann besteht die restliche Attacke nur noch aus l unabhängigen
Caesar-Entschlüsselungsverfahren.
s.a. www.weblearn.hs-bremen.de/risse/MAI/docs/mai1.pdf
k = KEY
Vigenère
Vigenère−1
x=
y=
x=
ABCDEFABCDEF
228
Problem 47(b)
Jeder Schlüssel besteht aus einer Zeichenkette k beliebiger Länge. Der
l
Schlüsselraum ist damit ∪∞
l=1 {0, 1, 2, . . . , 25} bei Verwendung etwa
des lateinischen Alphabets.
Die Sicherheit der Vigenère-Verschlüsselung ist also umso höher, je
länger der Schlüssel. Zugleich wachsen aber auch die Anforderungen
an die Übermittelung der Schlüssel an die Empfänger.
Höchste Sicherheit, bei gleichzeitig höchstem Aufwand für die Übermittelung der Schlüssel, bieten Schlüssel, die nur einmal verwendet
werden, one time pad, s.a. www.fourmilab.ch/onetime/otpjs.html
229
Problem 48(a)
Qn
Es gibt n! = 1 · 2 · 3 · · · n = i=1 i Permutationen von n Objekten.
Das lateinische Alphabet hat damit
26! = 403291461126605635584000000
Permutationen.
230
Problem 48(b)
Nein, weil weiterhin die Buchstaben-tupel-Häufigkeiten erhalten bleiben und für eine Entschlüsselung genutzt werden können.
z.B. Sei y = CESVLRHEESUUSLLGANOSGMIHRSTU.
S, C, und H liegen sehr dicht beieinander (Blockung), so daß man das
Trigramm SCH vermuten kann. Kleinstmögliche Block-Länge ` ist 5.
Für diese Block-Länge bekommt man die unwahrscheinlichen TextAnfänge ”ELVSCH. . . ” oder ”EVLSCH. . . ”. Bei ` = 6 ist SCH nicht
möglich; ` = 6 scheidet daher aus. Für ` = 7 ergibt sich:
...SCH....SEL....ALG.....HMU...
Die engültige Position der Trigramme ist noch unbekannt; durch Verwendung der übrigen Buchstaben-tupel-Häufigkeiten erhält man dann
x = VERSCHLUESSELUNGSALGORITHMUS
s.a. www.kryptoanalytiker.de
231
Problem 48(c)
Verschlüsselt wird also durch Permutation von Text-Blöcken fester
Länge. Im folgenden Beispiel
htsisitapoesrcteemssga.e
werden benachbarte Buchstaben vertauscht. Die Permutation (2, 1)
wird auf 2-Buchstaben Blöcke angewendet.
Es gibt n! Permutationen von Blöcken mit n Buchstaben: je länger
die Blöcke um so mehr Permutationen oder Schlüssel gibt es, d.h. um
so sicherer ist die Verschlüsselung durch Permutationen. Gleichzeitig
wachsen aber auch die Schlüssel und der Aufwand für die Pufferung
der zu verschlüsselnden bzw. zu entschlüsselnden Nachrichten.
232
Problem 49(a)
P inv
x=
y=
x=
40 8 48 16 56 24 64 32
38 6 46 14 54 22 62 30
=
36 4 44 12 52 20 60 28
34 2 42 10 50 18 58 26
This is a TOP secret message!
39 7 47 15 55 23 63 31
37 5 45 13 53 21 61 29
35 3 43 11 51 19 59 27
33 1 41 9 49 17 57 25
padding
DES-P
DES-P inv
? Warum wird wohl die codierte Zeichenkette als o |-String, also jeder
codierte Block von 8 Buchstaben als 64bit-Block dargestellt?
Probieren Sie andere padding characters, d.h. Buchstaben zum Auffüllen.
233
Problem 49(b)
inv
Sei fK
(L, R) = (R ⊕ K, L). Wegen K ⊕ K = ~0 gilt dann
inv
inv
fK
fK (L, R) = fK
(R, L ⊕ K) = (L ⊕ K ⊕ K, R) = (L, R)
wie auch
inv
fK fK
(L, R) = fK (R ⊕ K, L) = (L ⊕ K ⊕ K, R) = (L, R)
fK stellt eine Substitution dar, wenn 64bit Blöcke (L, R) als ein Buchstabe im Alphabet A = {0, 1}64 aufgefaßt werden.
x=
K=
y=
x=
This is a TOP secret message!
padding
key!
check
DES-f
DES-f inv
DES besteht nun aus insgesamt 16 solchen Substitutionen.
234
DES verschlüsselt eine Botschaft x durch iterierte Anwendung von
Funktionen fKi , wobei die Schlüssel Ki aus einem Haupt-Schlüssel K
erzeugt werden.
Verschlüsselung durch
y = P inv ◦ fK16 ◦ fK15 ◦ . . . ◦ fK2 ◦ fK1 ◦ P (x)
=
P inv (fK16 (fK15 (. . . (fK2 (fK1 (P (x)))) . . .)))
impliziert Entschlüsselung durch
x =
=
inv
inv
inv
inv
P inv ◦ fK
◦ fK
◦ . . . ◦ fK
◦ fK
◦ P (y)
1
2
15
16
inv
inv
inv
inv
P inv fK
fK
. . . fK
fK
(P (y)) . . .
1
2
15
16
235
Problem 49(c) L kann als Hintereinanderausführung von MatrixTransformationen aufgefaßt werden. L ist also linear. Allerdings sind
lineare Verschlüsselungsverfahren verhältnismäßig einfach zu brechen.
236
Problem 49(d) Die look up Tabelle für eine jede S-Box hat 26 Zeilen
à 4bit, also 28 = 256bit, insgesamt 8 · 256 = 211 = 2Kbit für die acht
S-Boxes.
Eine look up Tabelle für eine 32bit Substitution dagegen hätte 232
Zeilen à 32bit, also 32 · 4 · 230 = 128Gbit – eine völlig inakzeptable
Alternative.
Verwende vorab bestimmte inverse S-Boxes.
237
Problem 50(a) DES-Schlüssel sind 64bit lang; darin eingeschlossen
sind 8 parity bits. Die effektive Schlüssel-Länge ist also 56bit und die
Größe des Schlüsselraums ist 256 = 64 (210 )5 ≈ 64(103 )5 = 64 · 1015 .
238
Problem 50(b) Nur wenn mehrere DES-Verschlüsselungen nicht durch
eine einzige DES-Verschlüsselung emuliert werden können, d.h. nur
wenn
DESK2 ◦ DESK1 6= DESKo
gilt, dann bietet TDEA einen höhere Sicherheit als DES, s.a.
http://en.wikipedia.org/wiki/Triple DES
239
Problem 50(c) TDEA-Schlüssel sind 3×bit lang.
Die effektive Schlüssel-Länge ist also 168bit und die Größe des Schlüsselraums ist 2168 = 256 (210 )10 ≈ 256(103 )10 = 2.56 · 1032 .
240
Problem 50(d) 2001 wurde der Advanced Encryption Standard, AES
publiziert und 2002 standardisiert. AES ist der Gewinner einer öffentlichen Ausschreibung.
Im Gegenzug wurde 2004 die Rücknahme von DES bzw. TDEA angekündigt und 2005 durchgeführt.
241
Problem 51(a) Das Verfahren ist um so sicherer, je schwieriger es
ist, aus A und fA auf fA−1 zu schließen.
Funktionen fA mit folgenden Eigenschaften eigenen sich für Verschlüsselungsverfahren mit öffentlichen Schlüsseln:
• fA ist eineindeutig. (Der Klartext wird in Blöcke fester Länge
zerlegt; fA ist auf jeden entstehenden Block anzuwenden.)
• fA und fA−1 sind (möglichst) leicht zu berechnen. (Nachrichten
werden schnell codiert und auch wieder dekodiert.)
• Aus A und fA kann praktisch nicht auf fA−1 geschlossen werden. (Verschlüsselte Nachrichten können nur mit unvertretbar
hohem Aufwand entschlüsselt werden – am besten ist es, wenn
der Entschlüsselungsaufwand abgeschätzt und das Verfahren je
nach Sicherheitsanforderungen skaliert werden kann.)
Übrigens, solche Funktionen heißen auch trapdoor functions.
242
Problem 52(a)
Der Klartext wird in Blöcke fester Länge zerlegt, so daß die (ASCII-)
Zeichenfolge als (großes) x ∈ N mit x < n aufgefaßt und fe nacheinander auf jedes dieser x angewendet werden kann.
Die fe sind trapdoor Funktionen, denn
• fe ist auf X = {0, 1, 2, . . . , n − 1} eineindeutig, da fd = fe−1 :
d ist modulo-ϕ(n) invers zu e, d.h. d e ≡ 1 (mod ϕ(n)) oder
d e = v(p−1)(q−1)+1 für ein v ∈ N, so daß xd e = x · xv(p−1)(q−1) .
Laut Fermat’s kleinem Satz, FLT gilt für prime p und q
de
xp−1 = 1 mod p
x = x(xp−1 )v(q−1) = x · 1v(q−1) = x mod p
⇒ de
q−1
x
= 1 mod q
x = x(xq−1 )v(p−1) = x · 1v(p−1) = x mod q
Aus xde = x mod p und xde = x mod q folgt per Chinesischem
Restsatz für teilerfremde, also erst recht für prime p und q
xed = x mod (pq) = x mod n
• fe (x) bzw. fd (y) sind leicht zu bestimmen, da nur mehrfach
Produkte (m1 · m2 ) mod n für mi ∈ X zu berechnen sind.
243
• Je größer n umso schwieriger ist es, von fe , also von e und n,
auf d zu schließen.
Beispielsweise brauchten 1994 ca. 600 über das Internet vernetzte Rechner insgesamt 5000MIPS Jahre, um die 129-stellige Zahl
R-12922 in ihre 64- und 65-stelligen Primfaktoren zu zerlegen.
p=
e=
x=
y=
x=
59
47
q=
d=
71
1123
This is a top secret message
n=
4189
check&fill at random
RSAenc
RSAdec
Zum Test von z.B. ggT(e, ϕ(n)) = 1 steht der Euklid’sche Algorithmus
zur Verfügung.
22 D. Atkins, M. Graff, A.K. Lenstra, P.C. Leyland: The magic words are
squeamish ossifrage; Asiacrypt ’94, pp263-277, LNCS 917, Springer 1995
244
Problem 52(b)
Die Sicherheit des RSA-Verfahrens besteht in der Schwierigkeit, natürliche Zahlen n ∈ N mit 100 und mehr Dezimalstellen in ihre Primfaktoren zu zerlegen.
Das RSA-Verfahren ist um so sicherer, je größer n ist, vgl. z.B.
www.comp.mq.edu.au/courses/comp333/Lecture/
factoring and RSA 4.pdf
245
Problem 52(c)
Sei Alice’s bzw. Bob’s öffentlicher RSA-Schlüssel eA bzw. eB , mit
geheimen RSA-Schlüsseln dA bzw. dB .
Dann muß Alice an ihre Botschaft y = feB (x) als digitale Signatur
nur etwa y 0 = fdA (x) anhängen.
Bob entschlüsselt den ersten Teil y der empfangenen Botschaft zu x =
fdB (y) und verifiziert anhand des zweiten Teiles, daß x und feA (y 0 )
übereinstimmen. Da nur Alice dA kennt und daher nur sie y 0 erzeugt
haben kann, kann Bob sicher sein, eine Botschaft von Alice empfangen
zu haben.
Im Übrigen muß Alice als Signatur y 0 = fdA (x) nicht die ganze Botschaft x verwenden. Es genügt, einen sowohl dem Sender wie dem
Empfänger bekannten hash-Wert hash(x) zu verwenden.
Typische hash-Verfahren sind etwa MD4, MD5 oder SHA-1.
246
Problem 53(a) AES ist ein Block-orientiertes, symmetrisches (identische Schlüssel für Ver- und Entschlüsselung) Verschlüsselungsverfahren, das aus mehreren Runden von Substitutionen und Permutationen
besteht.
csrc.nist.gov/publications/fips/fips197/fips-197.pdf
247
Problem 53(b) AES verschlüsselt Klartext in 128bit = 16bytes =
4word Blöcken. AES erlaubt 128bit, 192bit und 256bit lange Schlüssel
mit jeweils 10, 12 oder 14 Verschlüsselungsrunden.
Problem 53(c)
248
Eine AES-Verschlüsselungsrunde besteht aus
• Substituieren eines jeden Bytes durch ein anderes per S-Box
• Permutieren der Zeilen des als 4 × 4-Byte-Matrix angeordneten
Blocks
• Permutieren der Spalten des als 4×4-Byte-Matrix angeordneten
Blocks
• Exklusives Odern (XOR) des Blocks mit einem Teil des expandierten Schlüssels
249
Problem 54(a) SubBytes(): Die Substitution eines Bytes b vermittels der AES S-Box ist spezifiziert als Berechnung des multiplikativen
Inversen b−1 in GF(28 ), gefolgt von der affinen Transformation
 0

   
b0
1 0 0 0 1 1 1 1
b0
1
b01 
 b1  1
b  1 
0 1 0 01 1 01 1 0 1 b0  1
1 1
1
 0
   
   
b  0
1 1 0 01 0 11 1 0 1 0
1 1
b2 
   
 b  1 
1
 0

 b2  0
b  1 1 1 0 0 0 1 1 b  0
b3 


   


1
1
1
1
0
0
0
1






 0  = b0 = Ab +b c =1 1 1 1 0 0 0 1 b  0
 b3  + 0
+0 . 0
=
b4 

 (5.2)
  
1
1
1
1
1
0
b  1 





1 1 1 1 0 0 0 b
0
 0
 b4  0
   





b5 
 b5  1
1 0 1 11 1 11 0 1 0 b1  1
1 0
b  0 
0

 0
   
b  0 
0 1 10 1 11 1 1 0 b1  1
1
b6 
0 b6  1
   0
    1
b  0 0 0 1 1 1 1 1 b  0
b07
0 0 0 1 1 1 1 1
b7
0
'
0
'
1
'
2
'
3
'
4
'
5
'
6
'
7
0
1
2
3
4
5
6
7
Figure 6 illustrates the effect of the SubBytes() transformation on the State.
s0,0 s0,1 s0, 2 s0,3
S-Box
s0' , 0 s0' ,1 s0' , 2 s0' ,3
s1, 0 s1,1 s1, 2 s1,3
s1' ,0
s2, 0 s2,1 s2, 2 s2 ,3
s2' , 0 s2' ,1 s2' , 2 s2' ,3
s3, 0 s3,1 s3, 2 s3,3
s3' ,0 s3' ,1 s3' , 2 s3' ,3
sr ,c
s1' ,1' s1' , 2
sr ,c
s1' ,3
Figure 6. SubBytes() applies the S-box to each byte of the State.
The S-box used in the SubBytes() transformation is presented in hexadecimal form in Fig. 7.
s3, 0 s3,1 s3, 2 s3,3
s3,0 s3,1 s3, 2 s3,3
Figure 6. SubBytes() applies the S-box to each byte of the State.
250
The S-box used in the SubBytes() transformation is presented in hexadecimal form in Fig. 7.
For example, if s1,1 = {53}, then the substitution value would be determined by the intersection
Die AES S-Box ist
üblicherweise
als
table
d.h.
of the row
with index ‘5’ and the column with
index look
‘3’ in Fig. 7. up
This would
result in s′implementiert,
having
1,1
InvShiftRows()
a value of {ed}.
s
s
s
y
s
s'
s'
s'
s'
0 r , 0 1 r ,1 2 r ,3
5
6
7
8
9 r , 0 a r ,1 b r , 2c r d
2
r4, 3
,3
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4
S
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5S ’ f1 71 d8
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27
sd6
sb3
s29
4 09 83 s2c
5a a0 52 s3b
e3
,1 s0 ,1b
2 s0 , 36e
0 ,1
0, 2
0,3
0, 0 s01a
0, 0
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c
s1fb
s02
s7f
s50
6 d0 ef s1aa
33 85 45 sf9
3c
,0
,1 s1,43
2 s1, 34d
1, 3
1, 0
1,1
1, 2
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff
x
8 cd 0c s13 s ec s 5f s 97 44 17 c4 sa7 s7e s3d s64 5d
2, 0
2 ,1
2, 2
2 ,3
2, 2
2 ,3
2, 0
2 ,1
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e
a e0 32 s3a s 0a s 49 s 06 24 5c c2 sd3 sac s62 s91 95
,0
3,1
2
3, 3
3,1
3, 2
3, 3
3, 0
b e7 c8 337
6d 3,8d
d5 4e a9 6c 56
f4
ea
65
7a
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd
Figure
three
the
d 70 13.
3eInvShiftRows()cyclically
b5 66 48 03 f6 0eshifts
61 the
35last57
b9rows
86 inc1
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54
e
f
ab 76
72 c0
31 15
b2 75
2f 84
58 cf
9f a8
f3 d2
19 73
0b db
e4 79
ae 08
8b 8a
State.
1d 9e
28 df
bb 16
5.3.2 InvSubBytes() Transformation
Figure 7. S-box: substitution values for the byte xy (in hexadecimal format).
InvSubBytes() is the inverse of the byte substitution transformation, in which the inverse Sbox is applied to each byte of the State. This is obtained by applying the inverse of the affine
16
transformation (5.1) followed by taking the multiplicative
inverse in GF(28).
wie ebenso die inverse S-Box
The inverse S-box used in the InvSubBytes() transformation is presented in Fig. 14:
y
0
1
2
3
4
5
6
7
x
8
9
a
b
c
d
e
f
0
52
7c
54
08
72
6c
90
d0
3a
96
47
fc
1f
60
a0
17
1
09
e3
7b
2e
f8
70
d8
2c
91
ac
f1
56
dd
51
e0
2b
2
6a
39
94
a1
f6
48
ab
1e
11
74
1a
3e
a8
7f
3b
04
3
d5
82
32
66
64
50
00
8f
41
22
71
4b
33
a9
4d
7e
4
30
9b
a6
28
86
fd
8c
ca
4f
e7
1d
c6
88
19
ae
ba
5
36
2f
c2
d9
68
ed
bc
3f
67
ad
29
d2
07
b5
2a
77
6
a5
ff
23
24
98
b9
d3
0f
dc
35
c5
79
c7
4a
f5
d6
7
38
87
3d
b2
16
da
0a
02
ea
85
89
20
31
0d
b0
26
8
bf
34
ee
76
d4
5e
f7
c1
97
e2
6f
9a
b1
2d
c8
e1
9
40
8e
4c
5b
a4
15
e4
af
f2
f9
b7
db
12
e5
eb
69
a
a3
43
95
a2
5c
46
58
bd
cf
37
62
c0
10
7a
bb
14
b
9e
44
0b
49
cc
57
05
03
ce
e8
0e
fe
59
9f
3c
63
c
81
c4
42
6d
5d
a7
b8
01
f0
1c
aa
78
27
93
83
55
d
f3
de
fa
8b
65
8d
b3
13
b4
75
18
cd
80
c9
53
21
e
d7
e9
c3
d1
b6
9d
45
8a
e6
df
be
5a
ec
9c
99
0c
f
fb
cb
4e
25
92
84
06
6b
73
6e
1b
f4
5f
ef
61
7d
Figure 14. Inverse S-box: substitution values for the byte xy (in
hexadecimal format).
22
shift (1,4) = 1 ; shift (2,4) = 2 ; shift (3,4) = 3 .
(5.4)
251
This has the effect of moving bytes to “lower” positions in the row (i.e., lower values of c in a
Problem
54(b)
ShiftRows():
Dieinto
Zeilen
eines
Blocks
zy- of
given row), while
the “lowest”
bytes wrap around
the “top”
of the
row (i.e.,werden
higher values
c in a given
row).
klisch
geschoben
wie der folgenden Darstellung zu entnehmen ist: der
Figure 8 S
illustrates
the in
ShiftRows()
Block
wird so
den Blocktransformation.
S 0 überführt.
ShiftRows()
sr , 0 sr ,1 sr , 2 sr ,3
sr' , 0 sr' ,1 sr' , 2 sr' ,3
S
S’
s0,0 s0,1 s0, 2 s0,3
s0,0 s0,1 s0, 2 s0,3
s1, 0 s1,1 s1, 2 s1,3
s1,1
s2, 0 s2,1 s2, 2 s2,3
s2, 2 s2,3 s2, 0 s2,1
s3, 0 s3,1 s3, 2 s3,3
s3,3 s3, 0 s3,1 s3, 2
s1, 2
s1,3
s1, 0
Figure 8. ShiftRows() cyclically shifts the last three rows in the State.
Die inverse Transformation schiebt Zeilen zyklisch in Gegenrichtung.
5.1.3 MixColumns() Transformation
The MixColumns() transformation operates on the State column-by-column, treating each
column as a four-term polynomial as described in Sec. 4.3. The columns are considered as
252
Problem
Polynome
als
 s0' , c  02 03 01 01  s0, c 
 '  
 
54(c)
Spalten eines Blocks (5.6)
werden
 =  01 02 03 01  s1, cDie
 s1, cMixColumns():

for 0 ≤ c < Nb.
 s2' , c   01 01 02 03  s2, c  8
mit Koeffizienten
in
GF(2
)
aufgefaßt
und
mit
 '  
 
 s3, c  03 01 01 02  s3, c 
3
2
1
0
a(x)
= multiplication,
0x03 x the
+four
0x01
xa column
+ 0x01
x +
0x02
x
As a result
of this
bytes in
are replaced
by the
following:
′ = ({02} • s ) ⊕ ({03} • s ) ⊕ s ⊕ s
1 multipliziert. Für die c-te Spalte gilt somit
modulo x4 s+
 0 s′ = s⊕ ({02} • s ) ⊕ ({03} • s ) ⊕ s




s0,c
0x02 0x03 0x01 0x01
s0,c
s0,c
′
s
s
⊕
s
⊕
({02}
•
s
)
⊕
({03}
•
s
)
=
s01,c  0x01 0x02 0x03 0x01 s1,c 


 • s ) ⊕ s ⊕ s ⊕ ({02} • s ).  
 0 s′ == ({03}
 = A s1,c 
s2,c  0x01




0x01 0x02 0x03
s2,c
s2,c 
0
0x03 0x01 0x01 0x02
s3,c
s3,c
s3,c
0 ,c
0 ,c
1,c
0 ,c
2 ,c
0 ,c
1,c
1,c
1,c
3, c
2 ,c
0 ,c
1,c
2 ,c
3, c
2 ,c
3, c
3, c
2 ,c
3, c
Figure 9 illustrates the MixColumns() transformation.
MixColumns()
s
s0,0 s00,,1c s0, 2 s0,3
s
s1, 0 s11,,1c s1, 2 s1,3
s2 , 0
ss2,c
2 ,1
s2 , 2 s2 , 3
s3, 0 ss33,,1c s3, 2 s3,3
s'
s0' , 0 s0' 0,1,c s0' , 2 s0' ,3
s1' ,0
s'
s1'1,1,c s1' , 2
s1' ,3
'
2, 0
'
ss2'2,1,c
s
s2' ,3
s3' ,0
'
s3'3,1,c
s3' , 2 s3' ,3
s
s
'
2, 2
Figure 9. MixColumns() operates on the State column-by-column.
Der Block S wird so in den Block S 0 überführt.
5.1.4 AddRoundKey() Transformation
In the AddRoundKey() transformation, a Round Key is added to the State by a simple bitwise
XOR operation. Each Round Key consists of Nb words from the key schedule (described in Sec.
253
Die inverse Transformation ergibt sich durch Multiplikation modulo
x4 + 1 mit dem Polynom
a−1 = 0x0b x3 + 0x0d x2 + 0x09 x1 + 0x0e x0
oder als Matrix-Transformation geschrieben
 0  




s0,c
0x0e 0x0b 0x0d 0x09
s0,c
s0,c
s01,c  0x09 0x0e 0x0b 0x09 s1,c 


−1 s1,c 
 0 =


s2,c  0x0d 0x09 0x0e 0x0b  s2,c  = A s2,c  .
0x0b 0x0d 0x09 0x0e
s3,c
s3,c
s03,c
254
Problem 54(d) AddRoundKey():
l = round * Nb
s0' ,c
s0,c
s0,0 s0,1 s0, 2 s0,3
s1,c
s1, 0 s1,1 s1, 2 s1,3
s2, 0 s2s,12,c s2, 2 s2,3
s3, 0 s3s,1 s3, 2 s3,3
3,c
⊕
wl+c
wl wl +1 wl + 2 wl + 3
'
0, 0
s
s0' ,1' s0' , 2 s0' ,3
s1,c
s1' ,0 s1' ,1 s1' , 2 s1' ,3
'
s2' , 0 ss2' ,12,c s2' , 2 s2' ,3
'
s3' ,0 s3s' ,13,c s3' , 2 s3' ,3
Wie bei
allen
stimmt
diese
Figure
10. XOR-Transformationen
AddRoundKey() XORs each column
of the
State Transformation
with a word
from the key schedule.
mit ihrer Inversen überein.
5.2
Key Expansion
The AES algorithm takes the Cipher Key, K, and performs a Key Expansion routine to generate a
key schedule. The Key Expansion generates a total of Nb (Nr + 1) words: the algorithm requires
an initial set of Nb words, and each of the Nr rounds requires Nb words of key data. The
resulting key schedule consists of a linear array of 4-byte words, denoted [wi ], with i in the range
0 ≤ i < Nb(Nr + 1).
The expansion of the input key into the key schedule proceeds according to the pseudo code in
Fig. 11.
255
Problem 55(a)
p
E = E(R) = Ea,b (R) = { x, ± x3 + ax + b : x3 + ax + b ≥ 0}
Elliptische Kurven sind offensichtlich Kurven der Ebene, symmetrisch
zur x-Achse. Abhängig von den Parametern a und b ist der Radikand
in einem Intervall oder in zwei Intervallen positiv. Entsprechend hat
E = E(R) = Ea,b (R) einen Ast oder zwei Äste. Vgl. z.B.
y
x
a = −4, b = 1
√
y
y
x
a = −3, b = 5
x
a = 5, b = −7
limx→+∞ ± x3 + ax + b = limx→+∞ ±x3/2 = ±∞
256
Problem 55(b)
Alle Koeffizienten von x3 + ax + b sind reell. Daher können die Nullstellen xi bequem trigonometrisch/hyperbolisch dargestellt
werden.
p
Sei p = a/3, q = b/2, D = p3 + q 2 und P = (sgn q) |p|.
x1
x2,3
p < 0, D ≤ 0
p < 0, D > 0
p>0
β = 13 arccos Pq3
β = 13 arcosh Pq3
β = 13 arsinh Pq3
−2P cos β
−2P cosh
−2P sinh
√ β
√ β
2P cos(β ± π/3) P (cosh β ± i 3 sinh β) P (sinh β ± i 3 cosh β)
257
Problem 55(c)
Bei gegebenem Radikanden x3 + ax + b sei wieder p = a/3, q = b/2
und Diskriminante D = p3 + q 2 . Dann bestimmt die Diskriminante
die Typen der Nullstellen.
D
D
D
D
>0
<0
= 0, q =
6 0
= 0, q = 0
eine reelle, zwei konjugiert komplexe Nullstellen
drei verschiedene reelle Nullstellen
eine einfache reelle, eine doppelte reelle Nullstelle
eine dreifache reelle Nullstelle
Es gibt also genau dann keine mehrfachen Nullstellen, wenn
D = p3 + q 2 =
a2
b2
+
6= 0
27
4
oder gleichbedeutend, wenn
108D = 108(p3 + q 2 ) = 4a2 + 27b2 6= 0
258
Problem 55(d) Die Gerade sei durch y = mx + c mit m 6= 0
gegeben. Die Abszisse x des Schnittpunktes der Geraden mit E löst
(mx + c)2 = x3 + ax + b oder gleichbedeutend
x3 − m2 x2 + (a − 2cm)x + b − c2 = 0
Die Substitution y = x − m2 /3 eliminiert den quadratischen Term.
Laut Voraussetzung hat die neue Gleichung
y 3 + 3py + 2q = 0
mit
3p = (a − 2cm) − 13 m4
2
2q = − 27
m6 + 13 (a − 2cm)m2 + b − c2
mindestens zwei einfache reelle Lösungen. Laut Klassifikation der Lösungen in Abhängigkeit von der Diskriminanten D = p3 + q 2 (auf
S. 257) muß es zu zwei einfachen reellen Lösungen eine weitere einfache
reelle Lösung geben.
259
Problem 55(e) Sei s = (yQ − yP )/(xQ − xP ) die Steigung und somit
y = y(x) = yP + s(x − xP ) die Gerade durch P und Q. Dann hat die
Gleichung
2
y 2 (x) = yP + s(x − xP ) = x3 + ax + b
oder eben
x3 − s2 x2 + (a + . . .)x + (b + . . .) = 0
die drei Lösungen xp , xQ und xR , wo xR die Abszisse des dritten
Schnittpunktes der Geraden durch P und Q mit E ist. Vergleich der
Koeffizienten von x2 liefert
−s2 = −xP − xQ − xR
oder eben
xR = s2 − xP − xQ
Spiegeln des dritten Schnittpunkts an der x-Achse liefert R = P + Q
mit
yR = − (yP + s(xR − xP ) = s(xP − xR ) − yP
260
Problem 56(a) Man kann P +P als das Ergebnis des Grenzprozesses
P +Q with E 3 Q → P auffassen. Im Limit wird dann aus der Geraden
durch P und Q die Tangente in P mit Steigung
d p 3
3x2 + a
3x2 + a
1
s=
x + ax + b = p 3 P
= P
dx
2 x + ax + b
2yP
xP
P
P
Also ist y = y(x) = yP + s(x − xP ) die Tangente in P . xP ist doppelte
Nullstelle der Gleichung
2
y 2 (x) = yP + s(x − xP ) = x3 + ax + b
Die andere einfache Nullstelle ist xR . Also ist R = (xR , yR ) = P + P
wie zuvor gegeben durch
xR = s2 − 2xP und yR = − yP + s(xR − xP ) = s(xP − xR ) − yP
261
Problem 56(b) Wegen der Symmetrie von E muß Q = −P gelten.
Die Gerade durch P und Q ist vertikal und schneidet E nur in genau
diesen beiden Punkten. Angenommen, daß wieder in einem Grenzprozeß E 3 Q0 → Q. Dann bewegt sich R := P + Q0 auf dem unbeschränkten Ast von E gegen Unendlich. Das Resultat dieses Grenzprozesses definiert nun einen besonderen Punkt auf E, den sogenannten
Punkt im Unendlichen oder kurz 0.
Verwendung homogener Koordinaten transformiert die Ebene zusammen mit der elliptischen Kurve in den projectiven Raum, was zeigt,
daß es nur einen Punkt im Unendlichen gibt [31].
262
Problem 56(c) Die Einführung von 0 zusammen mit der Definition
−P = −(xP , yP ) := (xP , −yP ) impliziert,
daß 0 ein neutrales oder Null-Element bzgl. dieser Addition ist und
daß −P das inverse Element von P bzgl. dieser Addition ist, d.h.
• P + 0 = 0 + P = P für alle P ∈ E
zudem gilt 0 + 0 = 0.
• P + (−P ) = (−P ) + P = P − P = 0 für alle P ∈ E
zudem ist 0 invers zu 0.
Die Gleichung P + Q = R löst Q = (−P ) + R für beliebige P, R ∈ E.
263
Problem 56(d)
Da diese so definierte Adition kommutativ ist, macht sie aus E =
Ea,b (R) eine (additive) kommutative Gruppe oder auch eine sogenannte Abel23 sche Gruppe.
23
Niels Henrik Abel (1802-1829)
www-history.mcs.st-andrews.ac.uk/Biographies/Abel.html
264
Problem 57(a) Alle Operationen in GF(p) (vgl. Arithmetik in
GF(p), S. 43) durchzuführen, macht E = Ea,b GF(p) zu einer kommutativen (additiven) Gruppe (bzgl. der Assoziativität dieser Addition vgl. [31]). Das neutrale Element, d.h. das Null-Element bzgl. der
Addition ist hier durch den Punkt (<leerer string>,infty) bezeichnet.
Elliptische Kurve E GF(p) = {(x, y) : y 2 = x3 + ax + b} über GF(p)
mit a = 1
b= 7
ist eine (addi und p = 17
tive) Gruppe mit card E GF(p) =
Elemen
√
ten, wobei laut Hasse24 |card E GF(p) − (p+1)| ≤ 2 p gilt. check
E GF(p) =
P = (xP , yP ) mit xP = 2
Q = (xQ , yQ ) mit xQ = 1
R = (xR , yR ) mit xR =
yP = 0
yQ = 3
yR =
R := P + Q
Q := −P
p&v25 reset
24
25
Helmut Hasse (1898-1979)
www-history.mcs.st-andrews.ac.uk/Biographies/Hasse.html
p&v = prüfe, ob P, Q ∈ E; vervollständige ggfls. die Felder P und Q
265
Problem 58(a) In GF(2m ) ist jedes Element r bzgl. der Addition zu
sich selbst invers, d.h. −r = r ∈ GF(2m ). Daher sind P = (x, y) mit
y 2 = x3 + ax + b und −P = (x, −y) identisch in E = Ea,b GF(2m ) ,
und es gilt 2P = P + P = P − P = 0 für jedes P ∈ E, so daß E
isomorph zu GF(2) × GF(2) × . . . × GF(2) ist.
Die von einem beliebigen Element erzeugten Untergruppen von E
haben also nur zwei Elemente, was jeden Einsatz in kryptographischen
Anwendungen ausschließt (vgl. diskretes Logarithmus-Problem). Lösungen zu Problemen
266
in
Problem 58(b) Alle Operationen in GF(2m ) (vgl. Arithmetik
GF(2m ), S. 45) durchzuführen, macht E = Ea,b GF(2m ) zu einer
kommutativen (additiven) Gruppe.
267
Problem 59(a) ECC ist ein Block-orientiertes, asymmetrisches public key Verschlüsselungsverfahren, das die Gruppen-Struktur auf elliptischen Kurven E = Ea,b (F) über F = GF(p) oder F = GF(2m )
nutzt.
Es gibt die EC-basierte Ver-/Entschlüsselung (ECIES), den EC DiffieHellman Schlüsselaustausch (ECDH), und den EC digitale Signatur
Algorithmus (ECDSA).
Wegen seiner hervorragenden Performance wird ECC vor allem dazu
benutzt, RSA in hybriden Verschlüsselungsverfahren zu ersetzen.
[30]
[32]
[31]
www.secg.org/collateral/sec1 final.pdf
www.iaik.tugraz.at/.../oswald/papers/Introduction to ECC.pdf
s.a. z.B. www.faqs.org/rfcs/rfc3278.html,
http://ducati.doc.ntu.ac.uk/uksim/journal/Vol-5/No-1&2/ROBERTS.pdf
268
Problem 59(b) Alle Teilnehmer einigen sich auf die Verwendung
einer elliptischen Kurve E = E(F) über einem endlichen Körper F
und auf einen geeigneten Generator G ∈ E. Sei n = card(< G >).
Jeder Teilnehmer wählt eine Zufallszahl 0 < r < n als geheimen
Schlüssel und veröffentlicht rG als öffentlichen Schlüssel.
wählt veröffentlicht
Alice
a
QA = aG
Bob
b
QB = bG
..
..
..
.
.
.
Um Bob eine verschlüsselte Botschaft m zu schicken, konvertiert Alice
m in M ∈ E, wählt eine Zufallszahl k und sendet die verschlüsselte
Botschaft, nämlich das Paar (kG, M + k(bG)) ∈ E × E an Bob.
Alice
Bob
wählt
k
verschlüsselt
(kG, M + kQB )
(kG, M + k(bG))
entschlüsselt
M = M + kbG − b(kG)
Bob entschlüsselt (kG, M + k(bG)), indem er M + k(bG) − b(kG) = M
berechnet.
269
Problem 59(c) Vor dem Schlüssel-Austausch verständigen sich Alice
und Bob auf eine öffentliche elliptische Kurve E = E(F) über einem
endlichen Körper F und auf einen Generator G ∈ E.
Sei n = card(< G >).
Jeder Partner wählt eine Zufallszahl r ∈ N mit 1 < r < n als geheimen
Schlüssel, veröffentlicht den dazugehörigen öffentlichen Schlüssel Q =
rG ∈ E und berechnet einen geheimen Schlüssel R ∈ E.
Alice
Bob
wählt
a
b
veröffentlicht
QA = aG
QB = bG
berechnet
RA = aQB
RB = bQA
Wegen
RA = aQB = abG = baG = bQA = RB
wissen dann Alice und Bob um dasselbe Geheimnis RA = R = RB ,
den gemeinsamen geheimen Schlüssel R.
270
Problem 59(d) Sei n = card(< G >). Alice will ihre Botschaft m
an Bob signieren. Ihr Schlüssel-Paar ist (a, Q) ∈ N × E mit geheimen
Schlüssel 1 < a < n und öffentlichem Schlüssel Q = aG.
wählt
Alice
k
hashes
berechnet
r = xkG mod n
e = hash(m) h = k −1 mod n
s = h(e + ar) mod n
signiert
(r, s)
Alice wählt zufällige 1 < k < n bis r 6= 0 und s 6= 0 gilt.
Bob empfängt Alices Botschaft m zusammen mit ihrer Signatur (r, s).
hashes
Bob
berechnet
verifiziert
w = s−1 mod n
e = hash(m) u = ew mod n, v = rw mod n xP == r
P = uG + vQ
s = k −1 (e + ar) mod n ⇐⇒ k = s−1 (e + ar) mod n. Also, modulo n
k ≡ s−1 (e + ar) ≡ s−1 e + s−1 ar ≡ we + w ar ≡ u + a rw ≡ u + va
so daß P = uG + vQ = uG + vaG = (u + va)G = kG und daher
xP = xkG = r folgt.
271
Problem 60(a) Erstens berücksichtigt diese Kodierung die SymbolHäufigkeit: je häufiger ein Symbol umso kürzer sein code. Zweitens ist
diese Kodierung wegen code(si ) ⊂ code(sj ) für i < j nicht Präfix-frei.
Drittens agiert 0 als code-Trenner.
Vermutlich gibt es bessere Kodierungen.
272
Problem 60(b) Eine Kodierung kann als etikettierter Graph mit
Wurzel dargestellt werden: die Menge {code(si ) : i = 1, . . . , n} der
codes ist gerade die Menge der labels seiner End-Knoten, d.h. Knoten
mit genau einer inzidenten Kante.
0
1
0=code(s1 )
0
10=code(s2 )
1
11=code(s3 )
Offensichtlich ist eine Kodierung Präfix-frei genau dann, wenn der sie
darstellende Graph ein Binär-Baum ist.
273
Problem 60(c) Die codes einer Präfix-freie Kodierung sind die Blätter
ihres darstellenden Baums. Die Blätter seien mit den zugehörigen
Häufigkeiten etikettiert. Jeder interne Knoten ist Wurzel genau eines
Teilbaumes und ist mit der Summe der labels aller anderen Knoten
dieses Teilbaumes zu etikettieren.
1 = f1 + f2 + f3
0
1
f2 + f3
0=code(s1 ) with f1
0
10=code(s1 ) with f2
1
11=code(s1 ) with f3
Wenn nun nur die Symbol-Häufigkeiten gegeben sind, muß der Baum
von den Blättern aus aufgebaut werden.
David A. Huffman: A method for the construction of minimum-redundancy
codes; Proceedings of the Institute of Radio Engineers, I.R.E. Sept
1952, S. 1098-1102 http://compression.ru/download/articles/huff/huffman 1952 minimum-redundancy-codes.pdf
274
Problem 61(a)
Der Einfachkeit halber bestehe das Alphabet aus etwa den 64 Zeichen
Leerzeichen (ASCII 32) bis hin zu Unterstrich (ASCII 95).
text Abrakadabra Abrakadabra
TEXT
pat=
chr=
init LZWstep
TXT
|dict| =
dict[
]=
check
reset
codes
old=
new=
init WZLstep
TEXT
|dict| =
dict[
]=
check
reset
275
Problem 61(b) Die modifizierte Dekompression des Algorithmus’:
Read OLD_CODE
CHARACTER = dict[oldCODE]; output CHARACTER
Read newCODE
IF newCODE is not in dictionary
PATTERN = dict[oldCODE]
PATTERN = PATTERN+CHARACTER
ELSE
PATTERN = dict[newCODE]
END of IF
output PATTERN
CHARACTER = first character in PATTERN
add dict[oldCODE] + CHARACTER to dictionary
oldCODE = newCODE
276
Problem 62(a) Die Anzahl der möglichen Fälle ist 3, nämlich RR,
RR und RB. Die Anzahl der günstigen Fälle ist 2, nämlich RB.
Somit ist P = P (RB) = 1/3.
277
Problem 62(b) a/A=Auto, z/Z=Ziege; kleine Buchstaben entsprechen zunächst gewählten Türen.
o.B.d.A. Kandidat wählt Tür No 1, Quizmaster öffnet Tür No 2.
Gewinn-Chancen ohne Revision: P (aZZ) = 1/3
Gewinn-Chancen mit Revision: P (zZA oder zZA) = 2/3
www.comedia.com/hot/monty.html oder (Monte-Carlo-) Experiment:
Türen
links
Mitte
1×
10 ×
100 ×
reset
rechts
Zustand
Wahl x bzw. Enthüllung o
Insgesamt
0
Treffer
0
Gewinn-Chance ≈
0
0
ohne
Revision in insgesamt 0
mit
Spielen, d.h.
ohne
Revision
mit
278
Problem 63(a) Unterscheidende Eigenschaften sind
• Datentyp und Wertebereich, wie z.B.
– 0-1-Zufallszahlen, etwa Münzwurf,
– natürliche oder ganze Zufallszahlen, etwa Dezimal-Ziffern
in der Dezimalbruchentwicklung von π,
– rationale Zufallszahlen, etwa die gemessenen Abstände von
Darts-Pfeilen zur Scheiben-Mitte,
– reelle Zufallszahlen, etwa freie Weglängen bei der Brownschen Bewegung eines Moleküls, usw.
• Verteilung der Zufallszahlen im zugehörigen Wertebereich, z.B.
– gleichverteilte 0-1-Zufallszahlen (0-1-Folgen), etwa Wurf einer (nicht manipulierten) Münze,
– Poisson-verteilte natürliche Zufallszahlen, etwa Anzahl radioaktiver Zerfälle pro Zeiteinheit,
– exponential-verteilte reelle Zufallszahlen, etwa Lebensdauer nicht-alternder Bauteile,
– normalverteilte reelle Zufallszahlen mit Mittelwert µ und
Standardabweichung σ, etwa physikalische Meßwerte, usw.
279
Als Standard-Zufallszahlen eignen sich im Einheitsintervall gleichverteilte, kontinuierliche Zufallszahlen X: aus X berechnet dann nämlich
if (X <= 0.5) return 0; else return 1;
gleichverteilte, diskrete Zufallszahlen Y ∈ {0, 1},
if (X < p1 ) return y1 ;
if (X < p1 + p2 ) return y2 ;
..
.
if (X < p1 + . . . + pn ) return yn ;
diskrete Zufallszahlen Y ∈ {y1 , y2 , . . . , yn } mit P (Y = yi ) = pi
für i = 1, 2, . . . , n,
(b-a)*X+a
im Intervall [a, b] ⊂ R gleichverteilte kontinuierliche Zufallszahlen,
round((b-a)*X+a)
im Intervall [a, b] ∩ Z gleichverteilte diskrete Zufallszahlen.
280
Für im Einheitsintervall gleichverteiltes X liefert allgemein F inv (X)
kontinuierliche Zufallszahlen Y = F inv (X) mit gegebener Verteilungsfunktion F und zugehöriger inverser
Funktion F inv , da P (Y < y) =
inv
P F (X) < y = P X < F (y) = F (y).
281
Problem 63(b) Es gibt eine ganze Reihe von Verfahren, PseudoZufallszahlen zu erzeugen. Alle Verfahren sind rekursiv: bekannt ist
z.B. J. v. Neumanns Methode der mittleren Ziffern von Quadraten
xn+1 = x2n 3b...b−1
für geeignetes 2b bit xo wobei x2n 3b...b−1 die mittleren 2b bit des 4b
bit Produktes x2n bezeichnet – oder besser und gebräuchlicher
xn+1 = a xn
mod m
für ein xo , etwa xo = 1, für einen geeigneten Faktor a in der Größenordnung 2b und für einen Modulus m = 2b , wenn integers mit b bits
dargestellt werden und es besonders auf Effizienz ankommt. Dieser
Generator ist ein Spezialfall der sogenannten Linear Congruential Generators
xn+1 = (a xn + c) mod m
für ein xo ∈ N, etwa xo = 1, und geeignete Parameter a, c, m ∈ N. Lösungen zu Problemen
282
Problem 63(c) xn+1 ∈ {0, 1, . . . m−1}. Die maximale Periodenlänge
ist also m. Für a = 1 und c = 0 ist sie 1.
283
Problem 64(a) Histogramme geben einen Eindruck davon, inwieweit die Zufallszahlen den Wertebereich gleichmäßig ausschöpfen. Dies
belegt die folgende Simulation: Da hier in JavaScript b = 64, werden
für m in der Größenordnung 232 , a in der Größenordnung 216 und
irgendein 0 ≤ c < m Zufallszahlen
yn = 2−r xn
mit xn+1 = (a xn + c)
mod m
erzeugt und die relative Häufigkeit ihres Auftretens in bestimmten
i
Intervallen beobachtet. Sei hi = round(100 P (Y = 2−r X ∈ [ i−1
5 , 5 ])).
00000
a = 1300103
h1 = 0
n= 0
%
c= 0
h2 = 0
1×
%
h3 = 0
10 ×
m = 4294967296
%
h4 = 0
100 ×
%
h5 = 0
test
1
%
reset
284
Problem 64(b) Die Entropie
E=−
9
X
pi log2 (pi )
i=0
d.h. der Informationsgehalt pro Dezimal-Ziffer (bit per decimal digit, bpdd), ist maximal für echte Zufallszahlen (mit unabhängigen
Ziffern). Die Entropie E ist (bei gleichverteilten Ziffern) maximal
Emax = −
9
X
1
1
1
log2 ( ) = − log2 ( ) ≈ 3.321928 bpdd
10
10
10
i=0
a = 1300103
c= 0
m = 4294967296
0000000000
n= 0
x= 1
1×
10 ×
100 ×
E= 0
test
reset
285
Problem 64(c) Pseudo-Zufallszahlen bilden Zeichenketten, die um
so schlechter zu komprimieren sind, je zufälliger die Pseudo-Zufallszahlen ausfallen. Sei die Komprimierbarkeit κ mit 0 ≤ κ ≤ 1 definiert
durch
κ=
komprimierte Pseudo-Zufallszahlen-Kettenlänge
unkomprimierte Pseudo-Zufallszahlen-Kettenlänge
unter Verwendung etwa der Huffman Kodierung. Die Komprimierbarkeit κ ist maximal 1 für echte Zufallszahlen.
286
Problem 64(d) Der statistische χ2 -Test prüft, ob zwei (Zufalls-)
Variable voneinander unabhängig sind. (Er ist verteilungsfrei, d.h. die
den Zufallsvariablen zugrunde liegenden Verteilungen sind irrelevant.)
Getestet wird nun, ob in einer Sequenz xi i=0,1,... von Zufallszahlen
bestimmte Paare (xi , xi+1 ) oder etwas allgemeiner (xi , xi+d ) für festes d ∈ N unabhängig sind. Hier seien x die Dezimal-Ziffern der
erzeugten Pseudo-Zufallszahlen und d = 1.
Dazu
y
x@
0
1
..
.
ist die sogenannte Kontingenz-Tabelle aufzustellen.
0
f0,0
f1,0
1
f0,1
f1,1
..
.
...
...
...
j
f0,j
f1,j
..
.
...
...
...
9
f0,9
f1,9
..
.
fi,∗
f0,∗
f1,∗
i
..
.
fi,0
fi,1
..
.
...
fi,j
..
.
...
fi,9
..
.
fi,∗
9
f9,0
f∗,0
f9,1
f∗,1
...
...
f9,j
f∗,j
...
...
f∗,j
f9,9
f∗,9
absolute Häufigkeit
fi,j = |{(i, j)}|
sowie absolute
Rand-Häufigkeiten
mit fi,∗ =
P9
j=0
fi,j
und
f∗,j =
P9
i=0 fi,j
f0,∗
n = # Beobachtungen
287
Dann ist die erwartetet Häufigkeit von (i, j) für unabhängige Variablen x and y
ei,j = n1 fi,∗ f∗,j
Genügend vielen Beobachtungen stellen hier sogar fi,j ≥ 10 und ei,j ≥
5 sicher – mehr als der χ2 -Test erfordert.
Die beiden Variablen sind umso abhängiger je größer die Abweichungen der beobachteten von den erwarteten Häufigkeiten ausfallen.
Die Prüfgröße χ2 ist χ2 -verteilt mit 9 · 9 = 81 Freiheitsgraden (df ).
χ2 =
9 X
9
9 X
9
2
X
X
fi,j
(fi,j − ei,j )2
=n
−1
ei,j
f f
i=0 j=0
i=0 j=0 i,∗ ∗,j
Die Quantile χ2df,α der χ2 -Verteilung sind für verschiedene df und
Signifikanz-Niveaus α tabelliert (hier für df = 81 interpoliert):
df \α
...
80
81
...
0.99
0.975
0.95
0.9
0.1
0.05
0.025
0.01
53.54
54.36
57.15
58.00
60.39
61.26
64.28
65.18
96.58
97.68
101.9
103.0
106.6
107.7
112.3
113.5
s. [36]
a = 1300103
y
x@
0
1
2
3
4
5
6
7
8
9
f∗,j
0
1
288
c= 0
2
3
m = 4294967296
4
5
6
7
8
9
fi,∗
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
α = 0.9
1×
x= 1
10 ×
100 ×
χ2 = 0
test
reset
289
Selbstverständlich kann derselbe Test für jedes d ∈ N durchgeführt
werden. Zudem kann die Folge der Zufallszahlen als bit-Kette aufgefaßt werden und so der Test auf Paare von bit-Ketten beliebiger aber
fester Länge in beliebigem aber festem Abstand angewandt werden.

Mathematische Puzzles - Weblearn

Transcrição

Documentos relacionados

Mod. ASP-1

Nachklausur zur Vorlesung Lineare Algebra I

Versuch 2: Addierer

Das Moderationssystem bei Knuddels

VORDÄCHER aus Aluminium und Edelstahl

Nr. 1, 2014 - ENTER

WLAN-Verschlüsselung WEP: Arbeitsweise und Designfehler

Kryptologie 1 - Institut für Informatik

Konfig4

206 S. 49

Logisches und Widersprüchliches