Cryptography with Mathematica

©2002-2023 by Gerald Teschl  <Gerald.Teschl@univie.ac.at>, <http://www.mat.univie.ac.at/~gerald/>

Note : Recent versions have built-in functionality for standard encryption algorithms.

?Encrypt

The point of this notebook is purely educational, that is, to demonstrate how the algorithms work. No efforts optimizing the code have been made! Comments are welcome.

Encoding and decoding strings

Encode and decode a given string using the simple encoding A=0, ... , Z=25 (stripping all other characters).

ToLetterCode[x_String]:=Select[ToCharacterCode[ToUpperCase[x]]-65,(0<=#≤25)&];
FromLetterCode[x_List]:=FromCharacterCode[x+65];

ToLetterCode["aBc"]

FromLetterCode[%]

Letter and digram frequencies

Compute the letter frequencies from a list of letters from an alphabet of n letters.

LetterFrequencies[x_List,n_Integer]:=Module[{l=Length[x],f=Table[0,{n}]},
Do[f[[ x[[i]] +1]]++,{i,l}];
N[((f )/l)]
];
DigramFrequencies[x_List,n_Integer]:=Module[{l=Length[x],f=Table[0,{n^2}]},
Do[f[[ x[[i]] + n x[[i+1]]+1]]++,{i,l-1}];
N[((f )/l)]
];

Generate some sample frequencies:

German

(* From https://de.wikipedia.org/wiki/Mathematik CC-by-sa-3.0 *)

GermanSampleText="Die Mathematik (die Kunst des Lernens, zum Lernen gehoerig) ist eine Wissenschaft, welche aus der Untersuchung von Geometrische Figur geometrischen Figuren und dem Rechnen mit Zahlen entstand. Fuer Mathematik gibt es keine allgemein anerkannte Definition; heute wird sie ueblicherweise als eine Wissenschaft beschrieben, die durch Logik logische Definitionen selbstgeschaffene Abstraktion abstrakte Mathematische Struktur Strukturen mittels der Logik auf ihre Eigenschaften und Muster untersucht.

 Geschichte 
Hauptartikel Geschichte der Mathematik
Die Mathematik ist eine der aeltesten Wissenschaften. Ihre erste Bluete erlebte sie noch vor der Antike in Mesopotamien, Indien und China. Spaeter in der Antike in Griechenland und im Hellenismus, von dort datiert die Orientierung an der Aufgabenstellung des rein logischen Beweisens und die erste Axiomatisierung, naemlich die euklidische Geometrie. Im Mittelalter ueberlebte sie unabhaengig voneinander im fruehen Humanismus der Universitaeten und in der arabischen Welt.

In der fruehen Neuzeit fuehrte François Viète Variablen ein und Rene Descartes eroeffnete durch die Verwendung von Koordinaten einen rechnerischen Zugang zur Geometrie. Die Beschreibung von Tangenten und die Bestimmung von Flaecheninhalten (Quadratur) fuehrte zur Infinitesimalrechnung von Gottfried Wilhelm Leibniz und Isaac Newton. Klassische Mechanik Newtons Mechanik und sein Gravitationsgesetz waren auch in den folgenden Jahrhunderten eine Quelle richtungweisender mathematischer Probleme wie das des Dreikoerperproblems.

Ein anderes Leitproblem der fruehen Neuzeit war das Loesen zunehmend komplizierter werdender algebraischer Gleichungen. Zu seiner Behandlung entwickelten Niels Henrik Abel und Évariste Galois den Begriff der Gruppe (Mathematik) Gruppe, der Beziehungen zwischen Symmetrien eines Objektes beschreibt. Als weitere Vertiefung dieser Untersuchungen koennen die neuere Algebra und insbesondere die algebraische Geometrie angesehen werden.

Eine damals neue Idee im Briefwechsel zwischen Blaise Pascal und Pierre de Fermat im Jahr 1654 fuehrte zur Loesung eines alten Problems, fuer das es schon andere, allerdings umstrittene Loesungsvorschlaege gab. Der Briefwechsel wird als Geburt der klassischen Wahrscheinlichkeitsrechnung angesehen. Die neuen Ideen und Verfahren eroberten viele Bereiche. Aber ueber Jahrhunderte hinweg kam es zur Aufspaltung der klassischen Wahrscheinlichkeitstheorie in separate Schulen. Versuche, den Begriff Wahrscheinlichkeit explizit zu definieren, gelangen nur fuer Spezialfaelle. Erst das Erscheinen von Andrei Kolmogorows Lehrbuch Grundbegriffe der Wahrscheinlichkeitsrechnung im Jahr 1933 schloss die Entwicklung der Fundamente moderner Wahrscheinlichkeitstheorie ab, siehe dazu auch 
Geschichte der Wahrscheinlichkeitsrechnung.

Im Laufe des 19. Jahrhunderts fand die Infinitesimalrechnung durch die Arbeiten von Augustin-Louis Cauchy und Karl Weierstrass ihre heutige Mathematische Strenge strenge Form. Die von Georg Cantor gegen Ende des 19. Jahrhunderts entwickelte Mengenlehre ist aus der heutigen Mathematik ebenfalls nicht mehr wegzudenken, auch wenn sie durch die Paradoxien des naiven Mengenbegriffs zunaechst deutlich machte, auf welch unsicherem Fundament die Mathematik vorher stand.

Die Entwicklung der ersten Haelfte des 20. Jahrhunderts stand unter dem Einfluss von David Hilberts Hilbertsche Probleme Liste von 23 mathematischen Problemen. Eines der Probleme war der Versuch einer vollstaendigen Axiomatisierung der Mathematik; gleichzeitig gab es starke Bemuehungen zur Abstraktion, also des Versuches, Objekte auf ihre wesentlichen Eigenschaften zu reduzieren. So entwickelte Emmy Noether die Grundlagen der modernen Algebra, Felix Hausdorff die allgemeine Topologie (Mathematik) Topologie als die Untersuchung Topologischer Raum topologischer Raeume, Stefan Banach den wohl wichtigsten Begriff der Funktionalanalysis, den nach ihm benannten Banachraum. Eine noch hoehere Abstraktionsebene, einen gemeinsamen Rahmen fuer die Betrachtung aehnlicher Konstruktionen aus verschiedenen Bereichen der Mathematik, schuf schliesslich die Einfuehrung der Kategorientheorie durch Samuel Eilenberg und Saunders Mac Lane.

 Inhalte und Methodik 
 Inhalte und Teilgebiete 
Hauptartikel Teilgebiete der Mathematik
Die folgende Aufzaehlung gibt einen ersten chronologischen Ueberblick ueber die Breite mathematischer Themen:
* das Rechnen mit Zahlen (Arithmetik - Altertum),
* die Untersuchung von Figuren (Geometrie - Altertum Die Hohe Bronzezeit Altertum, Euklid),
* das Aufloesen von Gleichungen (Algebra - Altertum Die Hohe Bronzezeit Altertum, Mittelalter und Renaissance, Nicolo Tartaglia Tartaglia),
* die Untersuchung der korrekten Schlussfolgerungen (Logik - Aristoteles) (teilweise nur zur Philosophie, oft aber auch zur Mathematik gezaehlt)
* Untersuchungen zur Teilbarkeit (Zahlentheorie - Euklid, Diophant von Alexandrien Diophant, Fermat, Leonhard Euler Euler, Carl Friedrich Gauss Gauss, Bernhard Riemann Riemann),
* das rechnerische Erfassen raeumlicher Beziehungen (Analytische Geometrie - Rene Descartes Descartes, 17. Jahrhundert),
* das Rechnen mit Wahrscheinlichkeiten (Wahrscheinlichkeitstheorie - Blaise Pascal, Jakob I. Bernoulli Jakob Bernoulli, Pierre-Simon Laplace, 17.-19. Jahrhundert),
* die Untersuchung von Funktionen, insbesondere deren Wachstum, Kruemmung, des Verhaltens im Unendlichen und der Flaecheninhalte unter den Kurven (Analysis - Isaac Newton Newton, Gottfried Wilhelm Leibniz Leibniz, Ende des 17. Jahrhunderts),
* die Beschreibung Feld (Physik) physikalischer Felder (Differentialgleichungen, partielle Differentialgleichungen, Vektoranalysis - Leonhard Euler Euler, die Bernoullis, Pierre-Simon Laplace Laplace, Carl Friedrich Gauss, Simeon Denis Poisson Poisson, Jean Baptiste Joseph Fourier Fourier, George Green Green, George Gabriel Stokes Stokes, David Hilbert Hilbert, 18.-19. Jahrhundert),
* die Perfektionierung der Analysis durch die Einbeziehung Komplexe Zahlen komplexer Zahlen (Funktionentheorie - Carl Friedrich Gauss Gauss, Augustin-Louis Cauchy, Karl Weierstrass, 19. Jahrhundert),
* die Geometrie gekruemmter Flaechen und Raeume (Differentialgeometrie - Carl Friedrich Gauss, Bernhard Riemann Riemann, Tullio Levi-Civita, 19. Jahrhundert),
* das systematische Studium von Symmetrien (Gruppentheorie - Evariste Galois, Niels Henrik Abel, Felix Klein, Sophus Lie, 19. Jahrhundert),
* die Aufklaerung von Paradoxien des Unendlichen (Mengenlehre und mathematische Logik - Georg Cantor Cantor, Gottlob Frege Frege, Bertrand Russell Russell, Ernst Zermelo Zermelo, Abraham Adolf Fraenkel Fraenkel, Anfang des 20. Jahrhunderts),
* die stetige Verformung geometrischer Koerper (Topologie (Mathematik) Topologie - Georg Cantor Cantor, Henri Poincare Poincare, Maurice Frechet Frechet, Felix Hausdorff Hausdorff, Kazimierz Kuratowski Kuratowski, Anfang des 20. Jahrhunderts),
* die Untersuchung von Strukturen und Theorien (Universelle Algebra, Kategorientheorie),
* die Erhebung und Auswertung von Daten (Mathematische Statistik).

Etwas abseits steht in dieser Aufzaehlung die Numerische Mathematik, die fuer konkrete kontinuierliche Probleme aus vielen der oben genannten Bereiche Algorithmus Algorithmen zur Loesung bereitstellt und diese untersucht.

Unterschieden werden ferner die reine Mathematik, auch theoretische Mathematik bezeichnet, die sich nicht mit aussermathematischen Anwendungen befasst, und die angewandte Mathematik wie zum Beispiel Versicherungsmathematik und Kryptologie. Die Uebergaenge der eben genannten Gebiete sind fliessend.

 Fortschreiten durch Problemloesen 

Kennzeichnend fuer die Mathematik ist weiterhin die Weise, wie sie durch das Bearbeiten von eigentlich zu schweren Problemen voranschreitet.

Sobald ein Grundschule Grundschueler das Addition Addieren natuerlicher Zahlen gelernt hat, ist er in der Lage, folgende Frage zu verstehen und durch Probieren zu beantworten: Welche Zahl muss man zu 3 addieren, um 5 zu erhalten? Die systematische Loesung solcher Aufgaben aber erfordert die Einfuehrung eines neuen Konzepts: der Subtraktion. Die Frage laesst sich dann umformulieren zu: Was ist 5 minus 3? Sobald aber die Subtraktion definiert ist, kann man auch die Frage stellen: Was ist 3 minus 5?, die auf eine negative Zahl und damit bereits ueber die Grundschulmathematik hinaus fuehrt.

Ebenso wie in diesem elementaren Beispiel beim individuellen Erlernen ist die Mathematik auch in ihrer Geschichte fortgeschritten: auf jedem erreichten Stand ist es moeglich, wohldefinierte Aufgaben zu stellen, zu deren Loesung weitaus anspruchsvollere Mittel noetig sind. Oft sind zwischen der Formulierung eines Problems und seiner Loesung viele Jahrhunderte vergangen und ist mit der Problemloesung schliesslich ein voellig neues Teilgebiet begruendet worden: so konnten mit der Infinitesimalrechnung im 17. Jahrhundert Probleme geloest werden, die seit der Antike offen waren.

Auch eine negative Antwort, der Beweis der Unloesbarkeit eines Problems, kann die Mathematik voranbringen: so ist aus gescheiterten Versuchen zur Aufloesung algebraischer Gleichungen die Gruppentheorie entstanden.

 Axiomatische Formulierung und Sprache 

Seit dem Ende des 19. Jahrhunderts, vereinzelt schon seit der Antike, wird die Mathematik in Form von Theorien praesentiert, die mit Aussagen beginnen, welche als wahr angesehen werden; daraus werden dann weitere wahre Aussagen hergeleitet. Diese Herleitung geschieht dabei nach genau festgelegten Schlussregeln. Die Aussagen, mit denen die Theorie anfaengt, nennt man Axiome, die daraus hergeleiteten nennt man Satz (Mathematik) Saetze. Die Herleitung selbst ist ein Beweis (Mathematik) Beweis des Satzes. In der Praxis spielen noch Definitionen eine Rolle, durch sie werden mathematische Begriffe durch Rueckfuehrung auf grundlegendere eingefuehrt und praezisiert. Aufgrund dieses Aufbaus der mathematischen Theorien bezeichnet man sie als axiomatische Theorien.

Ueblicherweise verlangt man dabei von Axiomen einer Theorie, dass diese widerspruchsfrei sind, also dass nicht gleichzeitig ein Satz und die Negation dieses Satzes wahr sind. Diese Widerspruchsfreiheit selbst laesst sich aber im Allgemeinen nicht innerhalb einer mathematischen Theorie beweisen (dies ist abhaengig von den verwendeten Axiomen). Das hat zur Folge, dass etwa die Widerspruchsfreiheit der Zermelo-Fraenkel-Mengenlehre, die fundamental fuer die moderne Mathematik ist, nicht ohne Zuhilfenahme weiterer Annahmen beweisbar ist.

Die von diesen Theorien behandelten Gegenstaende sind abstrakte mathematische Strukturen, die ebenfalls durch Axiome definiert werden. Waehrend in den anderen Wissenschaften die behandelten Gegenstaende vorgegeben sind und danach die Methoden zur Untersuchung dieser Gegenstaende geschaffen werden, ist bei der Mathematik umgekehrt die Methode vorgegeben und die damit untersuchbaren Gegenstaende werden erst danach erschaffen. In dieser Weise nimmt und nahm die Mathematik immer eine Sonderstellung unter den Wissenschaften ein.

Die Weiterentwicklung der Mathematik geschah und geschieht dagegen oft durch Sammlungen von Saetzen, Beweisen und Definitionen, die nicht axiomatisch strukturiert sind, sondern vor allem durch die Intuition und Erfahrung der beteiligten Mathematiker gepraegt sind. Die Umwandlung in eine axiomatische Theorie erfolgt erst spaeter, wenn weitere Mathematiker sich mit den dann nicht mehr ganz so neuen Ideen beschaeftigen.

Kurt Goedel zeigte um 1930 den nach ihm benannten Goedelscher Unvollstaendigkeitssatz Unvollstaendigkeitssatz, der besagt, dass es in jedem Axiomensystem klassischer Logik, das erlaubt, gewisse Aussagen ueber natuerliche Zahlen zu beweisen, entweder Aussagen gibt, die ebenso wenig wie ihre Negation beweisbar sind, oder aber das System selbst widerspruechlich ist.

Mathematik benutzt zur Beschreibung von Sachverhalten eine sehr kompakte Sprache, die auf Fachbegriffen und vor allem Formeln beruht. Eine Darstellung der in den Formeln benutzten Zeichen findet sich in der Liste mathematischer Symbole. Eine Besonderheit der mathematischen Fachsprache besteht in der Bildung von aus Mathematikernamen abgeleiteten Adjektiven wie Pythagoras pythagoreisch, euklidisch, Leonhard Euler eulersch, Niels Henrik Abel abelsch, Emmy Noether noethersch und Emil Artin artinsch.

 Anwendungsgebiete 

Die Mathematik ist in allen Wissenschaften anwendbar, die ausreichend Formalisierung formalisiert sind. Daraus ergibt sich ein enges Wechselspiel mit Anwendungen in empirischen Wissenschaften. Ueber viele Jahrhunderte hinweg hat die Mathematik Anregungen aus der Astronomie, der Geodaesie, der Physik und der Oekonomie aufgenommen und umgekehrt die Grundlagen fuer den Fortschritt dieser Faecher bereitgestellt. Beispielsweise hat Newton die Infinitesimalrechnung entwickelt, um das physikalische Konzept Kraft gleich Impulsaenderung mathematisch zu fassen. Fourier hat beim Studium der Wellengleichung die Grundlage fuer den modernen Funktion (Mathematik) Funktionsbegriff gelegt und Gauss hat im Rahmen seiner Beschaeftigung mit Astronomie und Landvermessung die Methode der kleinsten Quadrate entwickelt und das Loesen von linearen Gleichungssystemen systematisiert. Aus der anfaenglichen Untersuchung von Gluecksspielen ist die heute allgegenwaertige Statistik hervorgegangen.

Umgekehrt haben Mathematiker zuweilen Theorien entwickelt, die erst spaeter ueberraschende praktische Anwendungen gefunden haben. So ist zum Beispiel die schon im 16. Jahrhundert entstandene Theorie der Komplexe Zahl komplexen Zahlen zur mathematischen Darstellung des Elektromagnetismus inzwischen unerlaesslich geworden. Ein weiteres Beispiel ist der tensorielle Differentialformenkalkuel, den Albert Einstein Einstein fuer die mathematische Formulierung der Allgemeine Relativitaetstheorie allgemeinen Relativitaetstheorie verwendet hatte. Des Weiteren galt die Beschaeftigung mit der Zahlentheorie lange Zeit als intellektuelle Spielerei ohne praktischen Nutzen, ohne sie waeren heute allerdings die moderne Kryptographie und ihre vielfaeltigen Anwendungen im Internet nicht denkbar.
Siehe auch Angewandte Mathematik

 Verhaeltnis zu anderen Wissenschaften 
 Kategorisierung der Mathematik 

Ueber die Frage, zu welcher Kategorie der Wissenschaften die Mathematik gehoert, wird seit langer Zeit kontrovers diskutiert.

Viele mathematische Fragestellungen und Begriffe sind durch die Natur betreffende Fragen motiviert, beispielsweise aus der Physik oder den Ingenieurwissenschaften, und die Mathematik wird als Hilfswissenschaft in nahezu allen Naturwissenschaften herangezogen. Jedoch ist sie selbst keine Naturwissenschaft im eigentlichen Sinne, da ihre Aussagen nicht von Experimenten oder Beobachtungen abhaengen. Dennoch wird in der neueren Philosophie der Mathematik davon ausgegangen, dass auch die Methodik der Mathematik immer mehr derjenigen der Naturwissenschaft entspricht. Im Anschluss an Imre Lakatos wird eine Renaissance des Empirismus vermutet, wonach auch Mathematiker Hypothesen aufstellen und fuer diese Bestaetigungen suchen.

Die Mathematik hat methodische und inhaltliche Gemeinsamkeiten mit der Philosophie; beispielsweise ist die Logik ein Ueberschneidungsbereich der beiden Wissenschaften. Damit koennte man die Mathematik zu den Geisteswissenschaften rechnen, aber auch die Einordnung der Philosophie ist umstritten.

Auch aus diesen Gruenden kategorisieren einige die Mathematik - neben anderen Disziplinen wie der Informatik - als Strukturwissenschaft bzw. Formalwissenschaft.

An deutschen Universitaeten gehoert die Mathematik meistens zur selben Fakultaet (Hochschule) Fakultaet wie die Naturwissenschaften, und so wird Mathematikern nach der Promotion (Doktor) Promotion in der Regel der Akademischer Grad akademische Grad eines Dr. rer. nat. (Doktor der Naturwissenschaft) verliehen. Im Gegensatz dazu erreicht im englischen Sprachraum der Hochschulabsolvent die Titel Bachelor of Arts bzw. Master of Arts, welche eigentlich an Geisteswissenschaftler vergeben werden.

 Sonderrolle unter den Wissenschaften 

Eine Sonderrolle unter den Wissenschaften nimmt die Mathematik bezueglich der Gueltigkeit ihrer Erkenntnisse und der Mathematische Strenge Strenge ihrer Methoden ein. Waehrend beispielsweise alle naturwissenschaftlichen Erkenntnisse durch neue Experimente Falsifizierbarkeit falsifiziert werden koennen und daher prinzipiell vorlaeufig sind, werden mathematische Aussagen durch reine Gedankenoperationen auseinander hervorgebracht oder aufeinander zurueckgefuehrt und brauchen nicht Empirie empirisch ueberpruefbar zu sein. Dafuer muss aber fuer mathematische Erkenntnisse ein streng logischer Beweis (Mathematik) Beweis gefunden werden, bevor sie als Satz (Mathematik) mathematischer Satz anerkannt werden. In diesem Sinn sind mathematische Saetze prinzipiell endgueltige und allgemeingueltige Wahrheiten, sodass die Mathematik als die exakte Wissenschaft betrachtet werden kann. Gerade diese Exaktheit ist fuer viele Menschen das Faszinierende an der Mathematik. So sagte David Hilbert auf dem Internationaler Mathematikerkongress Internationalen Mathematiker-Kongress 1900 in Paris:

Zitat Wir eroertern noch kurz, welche berechtigten allgemeinen Forderungen an die Loesung eines mathematischen Problems zu stellen sind: ich meine vor allem die, dass es gelingt, die Richtigkeit der Antwort durch eine endliche Anzahl von Schluessen darzutun, und zwar auf Grund einer endlichen Anzahl von Voraussetzungen, welche in der Problemstellung liegen und die jedesmal genau zu formulieren sind. Diese Forderung der logischen Deduktion mittels einer endlichen Anzahl von Schluessen ist nichts anderes als die Forderung der Strenge in der Beweisfuehrung. In der Tat, die Forderung der Strenge, die in der Mathematik bekanntlich von sprichwoertlicher Bedeutung geworden ist, entspricht einem allgemeinen philosophischen Beduerfnis unseres Verstandes, und andererseits kommt durch ihre Erfuellung allein erst der gedankliche Inhalt und die Fruchtbarkeit des Problems zur vollen Geltung. Ein neues Problem, zumal, wenn es aus der aeusseren Erscheinungswelt stammt, ist wie ein junges Reis, welches nur gedeiht und Fruechte traegt, wenn es auf den alten Stamm, den sicheren Besitzstand unseres mathematischen Wissens, sorgfaeltig und nach den strengen Kunstregeln des Gaertners aufgepfropft wird.

Joseph Weizenbaum vom Massachusetts Institute of Technology bezeichnete die Mathematik als die Mutter aller Wissenschaften.

Zitat Ich behaupte aber, dass in jeder besonderen Naturlehre nur so viel eigentliche Wissenschaft angetroffen werden koenne, als darin Mathematik anzutreffen ist. Immanuel Kant Metaphysische Anfangsgruende der Naturwissenschaft, A VIII - (1786)

Die Mathematik ist daher auch eine kumulative Wissenschaft. Man kennt heute ueber 2000 mathematische Fachzeitschriften. Dies birgt jedoch auch eine Gefahr: durch neuere mathematische Gebiete geraten aeltere Gebiete in den Hintergrund. Neben sehr allgemeinen Aussagen gibt es auch sehr spezielle Aussagen, fuer die keine echte Verallgemeinerung bekannt ist. Donald E. Knuth schreibt dazu im Vorwort seines Buches Concrete Mathematics:

UebersetzungDer Veranstaltungstitel ,Konkrete Mathematik war urspruenglich als Gegenpol zur Abstrakten Mathematik gedacht, denn konkrete, klassische Errungenschaften wurden von einer neuen Welle abstrakter Vorstellungen - gemeinhin ,neue Mathematik genannt - in rasantem Tempo aus den Lehrplaenen gespuelt. Abstrakte Mathematik ist eine wunderbare Sache, an der nichts auszusetzen ist: Sie ist schoen, allgemeingueltig und nuetzlich. Aber ihre Anhaenger gelangten zu der irrigen Ansicht, dass die uebrige Mathematik minderwertig und nicht mehr beachtenswert sei. Das Ziel der Verallgemeinerung kam dermassen in Mode, dass eine ganze Generation von Mathematikern nicht mehr im Stande war, Schoenheit im Speziellen zu erkennen, die Loesung von quantitativen Problemen als Herausforderung zu begreifen oder den Wert mathematischer Techniken zu schaetzen. Die abstrakte Mathematik drehte sich nur noch um sich selbst und verlor den Kontakt zur Realitaet; in der mathematischen Ausbildung war ein konkretes Gegengewicht notwendig, um wieder ein stabiles Gleichgewicht herzustellen.

Es kommt somit der aelteren mathematischen Literatur eine besondere Bedeutung zu.

Der Mathematiker Claus Peter Ortlieb kritisiert die - seiner Ansicht nach - zu wenig reflektierte Anwendung der modernen Mathematik:

Zitat Man muss sich bewusst machen, dass die Erfassung der Welt durch Mathematik Grenzen hat. Die Annahme, sie funktioniere allein nach mathematischen Gesetzen, fuehrt dazu, dass man nur noch nach diesen Gesetzen Ausschau haelt. Natuerlich werde ich sie in den Naturwissenschaften auch finden, doch ich muss mir im Klaren darueber sein, dass ich die Welt durch eine Brille hindurch betrachte, die von vornherein grosse Teile ausblendet. Die mathematische Methode ist laengst von Wissenschaftlern fast aller Disziplinen uebernommen worden und wird in allen moeglichen Bereichen angewandt, wo sie eigentlich nichts zu suchen hat. Bedenklich sind Zahlen immer dann, wenn sie zu Normierungen fuehren, obwohl niemand mehr nachvollziehen kann, wie die Zahlen zustande gekommen sind.

 Mathematik in der Gesellschaft 
Das vom Bundesministerium fuer Bildung und Forschung (BMBF) seit dem Jahr 2000 jaehrlich ausgerichtete Wissenschaftsjahr war 2008 das Jahr der Mathematik.

 Mathematik als Schulfach 
Hauptartikel Mathematikunterricht
Mathematik spielt in der Schule eine wichtige Rolle als Pflichtfach. Mathematikdidaktik ist die Wissenschaft, die sich mit dem Lehren und Lernen von Mathematik beschaeftigt. In der Unter- und Mittelstufe geht es nicht nur um das Erlernen von Rechenfertigkeiten. In der Oberstufe werden dann Differential- und Integralrechnung sowie Analytische Geometrie/Lineare Algebra eingefuehrt und dazu Stochastik weitergefuehrt.

 Mathematik als Studienfach und Beruf 
Hauptartikel Mathematikstudium
Menschen, die sich beruflich mit der Entwicklung und der Anwendung der Mathematik beschaeftigen, nennt man Mathematiker.

Neben dem Mathematikstudium auf Diplom, in dem man seine Schwerpunkte auf reine und/oder angewandte Mathematik setzen kann, sind in neuerer Zeit vermehrt interdisziplinaere Studiengaenge wie Technomathematik, Wirtschaftsmathematik, Computermathematik oder Theoretische Biologie Biomathematik eingerichtet worden. Ferner ist das Lehramt an weiterfuehrenden Schulen und Hochschulen ein wichtiger mathematischer Berufszweig. An deutschen Universitaeten wird jetzt auch das Diplom auf Bachelor/Master-Studiengaenge umgestellt. Eine gewisse Anzahl an Semesterwochenstunden muessen auch angehende Informatiker, Chemiker, Biologen, Physiker, Geologen und Ingenieure belegen.

Die haeufigsten Arbeitgeber fuer Diplom-Mathematiker sind Versicherung (Kollektiv) Versicherungen, Kreditinstitut Banken und Unternehmensberatungen, insbesondere im Bereich mathematischer Finanzmodelle und Consulting, aber auch im IT-Bereich. Darueber hinaus werden Mathematiker in fast allen Branchen eingesetzt.

 Mathematische Museen und Sammlungen 
Mathematik ist eine der aeltesten Wissenschaften und auch eine experimentelle Wissenschaft. Diese beiden Aspekte lassen sich durch Museen und historische Sammlungen sehr gut verdeutlichen.

Die aelteste Einrichtung dieser Art in Deutschland ist der 1728 gegruendete Mathematisch-Physikalischer Salon Mathematisch-Physikalische Salon in Dresden. Das Arithmeum in Bonn am dortigen Institut fuer diskrete Mathematik geht in die 1970er Jahre zurueck und beruht auf der Sammlung von Rechengeraeten des Mathematikers Bernhard Korte. Das Heinz Nixdorf MuseumsForum (Abkuerzung HNF) in Paderborn ist das groesste deutsche Museum zur Entwicklung der Rechentechnik (insbesondere des Computers), und das Mathematikum in Giessen wurde 2002 von Albrecht Beutelspacher gegruendet und wird von ihm laufend weiterentwickelt. Im Museumsquartier in Wien befindet sich das von Rudolf Taschner geleitete Math.space, welches die Mathematik im Kontext zu Kultur und Zivilisation zeigt.

Darueber hinaus sind zahlreiche Spezialsammlungen an Universitaeten untergebracht, aber auch in umfassenderen Sammlungen wie zum Beispiel im Deutsches Museum Deutschen Museum in Muenchen oder im Deutsches Technikmuseum Berlin Museum fuer Technikgeschichte in Berlin (Rechner von Konrad Zuse entwickelt und gebaut).
";

GermanLetterFrequencies=LetterFrequencies[ToLetterCode[GermanSampleText],26];
GermanDigramFrequencies=DigramFrequencies[ToLetterCode[GermanSampleText],26];

Here are all the letter frequencies:

Transpose[{Table[FromCharacterCode[i+65],{i,0,25}],GermanLetterFrequencies*100}] //TableForm

Here are the five most common digrams:

f=Reverse[Ordering[GermanDigramFrequencies,-5]];Table[c=f[[i]];{FromCharacterCode[{Mod[c-1,26],Quotient[c-1,26]}+65],GermanDigramFrequencies[[c]]*100},{i,Length[f]}] //TableForm

GermanCharacterFrequencies=LetterFrequencies[ToCharacterCode[GermanSampleText],256];

Clear[f,c]

English

(* From https://en.wikipedia.org/wiki/Mathematics CC-by-sa-3.0 *)

EnglishSampleText="
Mathematics (from Ancient Greek, knowledge, study, learning) is the study of topics such as quantity (numbers), structure, space, and calculus There is a range of views among mathematicians and philosophers as to the exact scope and definition of mathematics.

Mathematicians seek out patterns and use them to formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proof. When mathematical structures are good models of real phenomena, then mathematical reasoning can provide insight or predictions about nature. Through the use of abstraction (mathematics)|abstraction and logic, mathematics developed from counting, calculation, measurement, and the systematic study of the shapes and motion (physics)|motions of physical objects. Practical mathematics has been a human activity for as far back as History of Mathematics|written records exist. The research required to solve mathematical problems can take years or even centuries of sustained inquiry.

Logic|Rigorous arguments first appeared in Greek mathematics, most notably in Euclids Euclids Elements|Elements. Since the pioneering work of Giuseppe Peano (1858-1932), David Hilbert (1862-1943), and others Foundations of mathematics|on axiomatic systems in the late 19th century, it has become customary to view mathematical research as establishing truth by Mathematical rigour|rigorous deductive reasoning|deduction from appropriately chosen axioms and definitions. Mathematics developed at a relatively slow pace until the Renaissance, when mathematical innovations interacting with new timeline of scientific discoveries|scientific discoveries led to a rapid increase in the rate of mathematical discovery that has continued to the present day.

Galileo Galilei (1564-1642) said, The universe cannot be read until we have learned the language and become familiar with the characters in which it is written. It is written in mathematical language, and the letters are triangles, circles and other geometrical figures, without which means it is humanly impossible to comprehend a single word. Without these, one is wandering about in a dark labyrinth. Carl Friedrich Gauss (1777-1855) referred to mathematics as the Queen of the Sciences. Benjamin Peirce (1809-1880) called mathematics the science that draws necessary conclusions. David Hilbert said of mathematics: We are not speaking here of arbitrariness in any sense. Mathematics is not like a game whose tasks are determined by arbitrarily stipulated rules. Rather, it is a conceptual system possessing internal necessity that can only be so and by no means otherwise. Albert Einstein (1879-1955) stated that as far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality. French mathematician Claire Voisin states There is creative drive in mathematics, its all about movement trying to express itself.

Mathematics is used throughout the world as an essential tool in many fields, including natural science, engineering, medicine, finance and the social sciences. Applied mathematics, the branch of mathematics concerned with application of mathematical knowledge to other fields, inspires and makes use of new mathematical discoveries, which has led to the development of entirely new mathematical disciplines, such as statistics and game theory. Mathematicians also engage in pure mathematics, or mathematics for its own sake, without having any application in mind. There is no clear line separating pure and applied mathematics, and practical applications for what began as pure mathematics are often discovered.


==History==

===Evolution===


The evolution of mathematics can be seen as an ever-increasing series of abstraction (mathematics)|abstractions. The first abstraction, which is shared by many animals, was probably that of numbers: the realization that a collection of two apples and a collection of two oranges (for example) have something in common, namely quantity of their members.


As evidenced by tally sticks|tallies found on bone, in addition to recognizing how to counting|count physical objects, prehistoric peoples may have also recognized how to count abstract quantities, like time - days, seasons, years.

More complex mathematics did not appear until around 3000 BC, when the Babylonians and Egyptians began using arithmetic, algebra and geometry for taxation and other financial calculations, for building and construction, and for astronomy. The earliest uses of mathematics were in trade|trading, land measurement, painting and weaving patterns and the recording of time.

In Babylonian mathematics elementary arithmetic (addition, subtraction, multiplication and division (mathematics)|division) first appears in the archaeological record. Numeracy pre-dated writing and numeral systems have been many and diverse, with the first known written numerals created by Ancient Egypt|Egyptians in Middle Kingdom of Egypt|Middle Kingdom texts such as the Rhind Mathematical Papyrus.

Between 600 and 300 BC the Ancient Greeks began a systematic study of mathematics in its own right with Greek mathematics.

Mathematics has since been greatly extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries continue to be made today. According to Mikhail B. Sevryuk, in the January 2006 issue of the Bulletin of the American Mathematical Society, The number of papers and books included in the Mathematical Reviews database since 1940 (the first year of operation of MR) is now more than 1.9 million, and more than 75 thousand items are added to the database each year. The overwhelming majority of works in this ocean contain new mathematical theorems and their mathematical proof|proofs.

===Etymology===
The word mathematics comes from the Ancient Greek, which, in the ancient Greek language, means that which is learnt, what one gets to know, hence also study and science, and in modern Greek just lesson. The word  is derived from  (manthano), while the modern Greek equivalent is  (mathaino), both of which mean to learn. In Greece, the word for mathematics came to have the narrower and more technical meaning mathematical study even in Classical times. Its adjective is , meaning related to learning or studious, which likewise further came to mean mathematical. In particular, meant the mathematical art.

In Latin, and in English until around 1700, the term mathematics more commonly meant astrology (or sometimes astronomy) rather than mathematics; the meaning gradually changed to its present one from about 1500 to 1800. This has resulted in several mistranslations: a particularly notorious one is Saint Augustines warning that Christians should beware of mathematici meaning astrologers, which is sometimes mistranslated as a condemnation of mathematicians.

The apparent plural form in English, like the French plural form (and the less commonly used singular derivative ), goes back to the Latin neuter plural (Cicero), based on the Greek plural, used by Aristotle (384-322 BC), and meaning roughly all things mathematical; although it is plausible that English borrowed only the adjective mathematic(al) and formed the noun mathematics anew, after the pattern of physics and metaphysics, which were inherited from the Greek. In English, the noun mathematics takes singular verb forms. It is often shortened to maths or, in English-speaking North America, math.

==Definitions of mathematics==
Aristotle defined mathematics as the science of quantity, and this definition prevailed until the 18th century. Starting in the 19th century, when the study of mathematics increased in rigor and began to address abstract topics such as group theory and projective geometry, which have no clear-cut relation to quantity and measurement, mathematicians and philosophers began to propose a variety of new definitions. Some of these definitions emphasize the deductive character of much of mathematics, some emphasize its abstractness, some emphasize certain topics within mathematics. Today, no consensus on the definition of mathematics prevails, even among professionals. There is not even consensus on whether mathematics is an art or a science. A great many professional mathematicians take no interest in a definition of mathematics, or consider it undefinable. Some just say, Mathematics is what mathematicians do.

Three leading types of definition of mathematics are called logicist, intuitionist, and Formalism (mathematics), each reflecting a different philosophical school of thought. All have severe problems, none has widespread acceptance, and no reconciliation seems possible.

An early definition of mathematics in terms of logic was Benjamin Peirces the science that draws necessary conclusions (1870). In the Principia Mathematica, Bertrand Russell and Alfred North Whitehead advanced the philosophical program known as logicism, and attempted to prove that all mathematical concepts, statements, and principles can be defined and proven entirely in terms of symbolic logic. A logicist definition of mathematics is Russells All Mathematics is Symbolic Logic (1903).

Intuitionist definitions, developing from the philosophy of mathematician L.E.J. Brouwer, identify mathematics with certain mental phenomena. An example of an intuitionist definition is Mathematics is the mental activity which consists in carrying out constructs one after the other. A peculiarity of intuitionism is that it rejects some mathematical ideas considered valid according to other definitions. In particular, while other philosophies of mathematics allow objects that can be proven to exist even though they cannot be constructed, intuitionism allows only mathematical objects that one can actually construct.

Formalism (mathematics)|Formalist definitions identify mathematics with its symbols and the rules for operating on them. Haskell Curry defined mathematics simply as the science of formal systems. A formal system is a set of symbols, or tokens, and some rules telling how the tokens may be combined into formulas. In formal systems, the word axiom has a special meaning, different from the ordinary meaning of a self-evident truth. In formal systems, an axiom is a combination of tokens that is included in a given formal system without needing to be derived using the rules of the system.

===Mathematics as science===

Carl Friedrich Gauss|Gauss referred to mathematics as the Queen of the Sciences. In the original Latin Regina Scientiarum, as well as in German language, the word corresponding to science means a field of knowledge, and this was the original meaning of science in English, also; mathematics is in this sense a field of knowledge. The specialization restricting the meaning of science to natural science follows the rise of Baconian method|Baconian science, which contrasted natural science to scholasticism, the Organon|Aristotelean method of inquiring from first principles. The role of empirical experimentation and observation is negligible in mathematics, compared to natural sciences such as experimental psychology|psychology, biology, or physics. Albert Einstein stated that as far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality. More recently, Marcus du Sautoy has called mathematics the Queen of Science ... the main driving force behind scientific discovery.

Many philosophers believe that mathematics is not experimentally falsifiability|falsifiable, and thus not a science according to the definition of Karl Popper. However, in the 1930s Goedels incompleteness theorems convinced many mathematicians that mathematics cannot be reduced to logic alone, and Karl Popper concluded that most mathematical theories are, like those of physics and biology, hypothesis|hypothetico-deductive: pure mathematics therefore turns out to be much closer to the natural sciences whose hypotheses are conjectures, than it seemed even recently. Other thinkers, notably Imre Lakatos, have applied a version of falsificationism to mathematics itself.

An alternative view is that certain scientific fields (such as theoretical physics) are mathematics with axioms that are intended to correspond to reality. The theoretical physicist J.M. Ziman proposed that science is public knowledge, and thus includes mathematics. Mathematics shares much in common with many fields in the physical sciences, notably the deductive reasoning|exploration of the logical consequences of assumptions. Intuition (knowledge)|Intuition and experimentation also play a role in the formulation of conjectures in both mathematics and the (other) sciences. Experimental mathematics continues to grow in importance within mathematics, and computation and simulation are playing an increasing role in both the sciences and mathematics.

The opinions of mathematicians on this matter are varied. Many mathematicians feel that to call their area a science is to downplay the importance of its aesthetic side, and its history in the traditional seven liberal arts; others feel that to ignore its connection to the sciences is to turn a blind eye to the fact that the interface between mathematics and its applications in science and engineering has driven much development in mathematics. One way this difference of viewpoint plays out is in the philosophical debate as to whether mathematics is created (as in art) or discovered (as in science). It is common to see university|universities divided into sections that include a division of Science and Mathematics, indicating that the fields are seen as being allied but that they do not coincide. In practice, mathematicians are typically grouped with scientists at the gross level but separated at finer levels. This is one of many issues considered in the philosophy of mathematics.

==Inspiration, pure and applied mathematics, and aesthetics==

Mathematics arises from many different kinds of problems. At first these were found in commerce, land measurement, architecture and later astronomy; today, all sciences suggest problems studied by mathematicians, and many problems arise within mathematics itself. For example, the physicist Richard Feynman invented the path integral formulation of quantum mechanics using a combination of mathematical reasoning and physical insight, and todays string theory, a still-developing scientific theory which attempts to unify the four Fundamental interaction|fundamental forces of nature, continues to inspire new mathematics.

Some mathematics is relevant only in the area that inspired it, and is applied to solve further problems in that area. But often mathematics inspired by one area proves useful in many areas, and joins the general stock of mathematical concepts. A distinction is often made between pure mathematics and applied mathematics. However pure mathematics topics often turn out to have applications, e.g. number theory in cryptography. This remarkable fact, that even the purest mathematics often turns out to have practical applications, is what Eugene Wigner has called The Unreasonable Effectiveness of Mathematics in the Natural Sciences|the unreasonable effectiveness of mathematics. As in most areas of study, the explosion of knowledge in the scientific age has led to specialization: there are now hundreds of specialized areas in mathematics and the latest Mathematics Subject Classification runs to 46 pages. Several areas of applied mathematics have merged with related traditions outside of mathematics and become disciplines in their own right, including statistics, operations research, and computer science.

For those who are mathematically inclined, there is often a definite aesthetic aspect to much of mathematics. Many mathematicians talk about the elegance of mathematics, its intrinsic aesthetics and inner beauty. Simplicity and generality are valued. There is beauty in a simple and elegant proof (mathematics)|proof, such as Euclids proof that there are infinitely many prime numbers, and in an elegant numerical method that speeds calculation, such as the fast Fourier transform. G.H. Hardy in A Mathematicians Apology expressed the belief that these aesthetic considerations are, in themselves, sufficient to justify the study of pure mathematics. He identified criteria such as significance, unexpectedness, inevitability, and economy as factors that contribute to a mathematical aesthetic.> Mathematicians often strive to find proofs that are particularly elegant, proofs from The Book of God according to Paul Erdoes. The popularity of recreational mathematics is another sign of the pleasure many find in solving mathematical questions.

==Notation, language, and rigor==

Most of the mathematical notation in use today was not invented until the 16th century. Before that, mathematics was written out in words, a painstaking process that limited mathematical discovery. Leonhard Euler (1707-1783) was responsible for many of the notations in use today. Modern notation makes mathematics much easier for the professional, but beginners often find it daunting. It is extremely compressed: a few symbols contain a great deal of information. Like musical notation, modern mathematical notation has a strict syntax (which to a limited extent varies from author to author and from discipline to discipline) and encodes information that would be difficult to write in any other way.

Mathematical language can be difficult to understand for beginners. Words such as or and only have more precise meanings than in everyday speech. Moreover, words such as open set|open and field (mathematics)|field have been given specialized mathematical meanings. Technical terms such as homeomorphism and Integral|integrable have precise meanings in mathematics. Additionally, shorthand phrases such as iff for if and only if belong to mathematical jargon. There is a reason for special notation and technical vocabulary: mathematics requires more precision than everyday speech. Mathematicians refer to this precision of language and logic as rigor.

Mathematical proof is fundamentally a matter of rigor. Mathematicians want their theorems to follow from axioms by means of systematic reasoning. This is to avoid mistaken theorems, based on fallible intuitions, of which many instances have occurred in the history of the subject. The level of rigor expected in mathematics has varied over time: the Greeks expected detailed arguments, but at the time of Isaac Newton the methods employed were less rigorous. Problems inherent in the definitions used by Newton would lead to a resurgence of careful analysis and formal proof in the 19th century. Misunderstanding the rigor is a cause for some of the common misconceptions of mathematics<!--This part needs improvement |>>-->. Today, mathematicians continue to argue among themselves about computer-assisted proofs. Since large computations are hard to verify, such proofs may not be sufficiently rigorous.

Axioms in traditional thought were self-evident truths, but that conception is problematic. At a formal level, an axiom is just a string of symbols, which has an intrinsic meaning only in the context of all derivable formulas of an axiomatic system. It was the goal of Hilberts program to put all of mathematics on a firm axiomatic basis, but according to Gödels incompleteness theorem every (sufficiently powerful) axiomatic system has independence (mathematical logic)|undecidable formulas; and so a final axiomatization of mathematics is impossible. Nonetheless mathematics is often imagined to be (as far as its formal content) nothing but set theory in some axiomatization, in the sense that every mathematical statement or proof could be cast into formulas within set theory.

==Fields of mathematics==

Mathematics can, broadly speaking, be subdivided into the study of quantity, structure, space, and change (i.e. arithmetic, algebra, geometry, and mathematical analysis|analysis). In addition to these main concerns, there are also subdivisions dedicated to exploring links from the heart of mathematics to other fields: to mathematical logic|logic, to set theory (foundations of mathematics|foundations), to the empirical mathematics of the various sciences (applied mathematics), and more recently to the rigorous study of uncertainty. 
While some areas might seem unrelated, the Langlands program has found   connections between areas previously thought unconnected, such as Galois groups, Riemann surfaces and number theory.

===Foundations and philosophy===
In order to clarify the foundations of mathematics, the fields of mathematical logic and set theory were developed. Mathematical logic includes the mathematical study of logic and the applications of formal logic to other areas of mathematics; set theory is the branch of mathematics that studies set (mathematics)|sets or collections of objects. Category theory, which deals in an abstract way with mathematical structures and relationships between them, is still in development. The phrase crisis of foundations describes the search for a rigorous foundation for mathematics that took place from approximately 1900 to 1930. Some disagreement about the foundations of mathematics continues to the present day. The crisis of foundations was stimulated by a number of controversies at the time, including the controversy over Cantors theory|controversy over Cantors set theory and the Brouwer-Hilbert controversy.

Mathematical logic is concerned with setting mathematics within a rigorous axiomatic framework, and studying the implications of such a framework. As such, it is home to Gödels incompleteness theorems which (informally) imply that any effective formal system that contains basic arithmetic, if sound (meaning that all theorems that can be proven are true), is necessarily incomplete (meaning that there are true theorems which cannot be proved in that system). Whatever finite collection of number-theoretical axioms is taken as a foundation, Gödel showed how to construct a formal statement that is a true number-theoretical fact, but which does not follow from those axioms. Therefore, no formal system is a complete axiomatization of full number theory. Modern logic is divided into recursion theory, model theory, and proof theory, and is closely linked to theoretical computer science, as well as to category theory.

Theoretical computer science includes computability theory (computation)|computability theory, computational complexity theory, and information theory. Computability theory examines the limitations of various theoretical models of the computer, including the most well-known model - the Turing machine. Complexity theory is the study of tractability by computer; some problems, although theoretically solvable by computer, are so expensive in terms of time or space that solving them is likely to remain practically unfeasible, even with the rapid advancement of computer hardware. A famous problem is the P = NP problem| problem, one of the Millennium Prize Problems. Finally, information theory is concerned with the amount of data that can be stored on a given medium, and hence deals with concepts such as data compression|compression and Entropy (information theory)|entropy.


===Pure mathematics===

====Quantity====
The study of quantity starts with numbers, first the familiar natural numbers and integers (whole numbers) and arithmetical operations on them, which are characterized in arithmetic. The deeper properties of integers are studied in number theory, from which come such popular results as Fermats Last Theorem. The twin prime conjecture and Goldbachs conjecture are two unsolved problems in number theory.

As the number system is further developed, the integers are recognized as a subset of the rational numbers (Fraction (mathematics)|fractions). These, in turn, are contained within the real numbers, which are used to represent Continuous function|continuous quantities. Real numbers are generalized to complex numbers. These are the first steps of a hierarchy of numbers that goes on to include quaternions and octonions. Consideration of the natural numbers also leads to the transfinite numbers, which formalize the concept of infinity. Another area of study is size, which leads to the cardinal numbers and then to another conception of infinity: the aleph numbers, which allow meaningful comparison of the size of infinitely large sets.


====Structure====
Many mathematical objects, such as set (mathematics)|sets of numbers and function (mathematics)|functions, exhibit internal structure as a consequence of operation (mathematics)|operations or relation (mathematics)|relations that are defined on the set. Mathematics then studies properties of those sets that can be expressed in terms of that structure; for instance number theory studies properties of the set of integers that can be expressed in terms of arithmetic operations. Moreover, it frequently happens that different such structured sets (or mathematical structure|structures) exhibit similar properties, which makes it possible, by a further step of abstraction, to state axioms for a class of structures, and then study at once the whole class of structures satisfying these axioms. Thus one can study group (mathematics)|groups, ring (mathematics)|rings, field (mathematics)|fields and other abstract systems; together such studies (for structures defined by algebraic operations) constitute the domain of abstract algebra.

By its great generality, abstract algebra can often be applied to seemingly unrelated problems; for instance a number of ancient problems concerning compass and straightedge constructions were finally solved using Galois theory, which involves field theory and group theory. Another example of an algebraic theory is linear algebra, which is the general study of vector spaces, whose elements called vector (geometric)|vectors have both quantity and direction, and can be used to model (relations between) points in space. This is one example of the phenomenon that the originally unrelated areas of geometry and algebra have very strong interactions in modern mathematics. Combinatorics studies ways of enumerating the number of objects that fit a given structure.


====Space====
The study of space originates with geometry - in particular, Euclidean geometry. Trigonometry is the branch of mathematics that deals with relationships between the sides and the angles of triangles and with the trigonometric functions; it combines space and numbers, and encompasses the well-known Pythagorean theorem. The modern study of space generalizes these ideas to include higher-dimensional geometry, non-Euclidean geometries (which play a central role in general relativity) and topology. Quantity and space both play a role in analytic geometry, differential geometry, and algebraic geometry. Convex geometry|Convex and discrete geometry were developed to solve problems in geometry of numbers|number theory and functional analysis but now are pursued with an eye on applications in convex optimization|optimization and computational geometry|computer science. Within differential geometry are the concepts of fiber bundles and calculus on manifolds, in particular, vector calculus|vector and tensor calculus. Within algebraic geometry is the description of geometric objects as solution sets of polynomial equations, combining the concepts of quantity and space, and also the study of topological groups, which combine structure and space. Lie groups are used to study space, structure, and change. Topology in all its many ramifications may have been the greatest growth area in 20th-century mathematics; it includes point-set topology, set-theoretic topology, algebraic topology and differential topology. In particular, instances of modern-day topology are metrizability theory, axiomatic set theory, homotopy theory, and Morse theory. Topology also includes the now solved Poincaré conjecture, and the still unsolved areas of the Hodge conjecture. Other results in geometry and topology, including the four color theorem and Kepler conjecture, have been proved only with the help of computers.



====Change====
Understanding and describing change is a common theme in the natural sciences, and calculus was developed as a powerful tool to investigate it. Function (mathematics)|Functions arise here, as a central concept describing a changing quantity. The rigorous study of real numbers and functions of a real variable is known as real analysis, with complex analysis the equivalent field for the complex numbers. Functional analysis focuses attention on (typically infinite-dimensional) Space Mathematics|spaces of functions. One of many applications of functional analysis is quantum mechanics. Many problems lead naturally to relationships between a quantity and its rate of change, and these are studied as differential equations. Many phenomena in nature can be described by dynamical systems; chaos theory makes precise the ways in which many of these systems exhibit unpredictable yet still deterministic system (mathematics)|deterministic behavior.


===Applied mathematics===
Applied mathematics concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, applied mathematics is a mathematical science with specialized knowledge. The term applied mathematics also describes the professional specialty in which mathematicians work on practical problems; as a profession focused on practical problems, applied mathematics focuses on the formulation, study, and use of mathematical models in science, engineering, and other areas of mathematical practice.

In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for its own sake. Thus, the activity of applied mathematics is vitally connected with research in pure mathematics.

====Statistics and other decision sciences====
Applied mathematics has significant overlap with the discipline of statistics, whose theory is formulated mathematically, especially with probability theory. Statisticians (working as part of a research project) create data that makes sense with random sampling and with randomized design of experiments|experiments; the design of a statistical sample or experiment specifies the analysis of the data (before the data be available). When reconsidering data from experiments and samples or when analyzing data from observational study|observational studies, statisticians make sense of the data using the art of statistical model|modelling and the theory of statistical inference|inference - with model selection and estimation theory|estimation; the estimated models and consequential Scientific method Predictions from the hypothesis|predictions should be statistical hypothesis testing|tested on Scientific method Evaluation and improvement|new data.

Statistical theory studies statistical decision theory|decision problems such as minimizing the risk (expected loss) of a statistical action, such as using a statistical method|procedure in, for example, parameter estimation, hypothesis testing, and selection algorithm|selecting the best. In these traditional areas of mathematical statistics, a statistical-decision problem is formulated by minimizing an objective function, like expected loss or cost, under specific constraints: For example, designing a survey often involves minimizing the cost of estimating a population mean with a given level of confidence. Because of its use of mathematical optimization|optimization, the mathematical theory of statistics shares concerns with other decision sciences, such as operations research, control theory, and mathematical economics.

====Computational mathematics====
Computational mathematics proposes and studies methods for solving mathematical problems that are typically too large for human numerical capacity. Numerical analysis studies methods for problems in analysis (mathematics)|analysis using functional analysis and approximation theory; numerical analysis includes the study of approximation and discretization broadly with special concern for rounding errors. Numerical analysis and, more broadly, scientific computing also study non-analytic topics of mathematical science, especially algorithmic numerical linear algebra|matrix and graph theory. Other areas of computational mathematics include computer algebra and symbolic computation.

==Mathematical awards==
Arguably the most prestigious award in mathematics is the Fields Medal, established in 1936 and now awarded every four years. The Fields Medal is often considered a mathematical equivalent to the Nobel Prize.

The Wolf Prize in Mathematics, instituted in 1978, recognizes lifetime achievement, and another major international award, the Abel Prize, was introduced in 2003. The Chern Medal was introduced in 2010 to recognize lifetime achievement. These accolades are awarded in recognition of a particular body of work, which may be innovational, or provide a solution to an outstanding problem in an established field.

A famous list of 23 open problems, called Hilberts problems, was compiled in 1900 by German mathematician David Hilbert. This list achieved great celebrity among mathematicians, and at least nine of the problems have now been solved. A new list of seven important problems, titled the Millennium Prize Problems, was published in 2000. A solution to each of these problems carries a $1 million reward, and only one (the Riemann hypothesis) is duplicated in Hilberts problems.

==Common misconceptions==
Mathematics is not a closed intellectual system, in which everything has already been worked out. There is no shortage of unsolved problems in mathematics|open problems. Every month, mathematicians publish many thousands of papers that embody new discoveries in the field.

Mathematics is not numerology; it is not concerned with supernatural properties of numbers. It is not accountancy; nor is it restricted to arithmetic.

Pseudomathematics is a form of mathematics - like activity undertaken outside academia, and occasionally by mathematicians themselves. It often consists of determined attacks on famous questions, consisting of proof-attempts made in an isolated way (that is, long papers not supported by previously published theory). The relationship to generally accepted mathematics is similar to that between pseudoscience and real science. The misconceptions involved are normally based on:
*misunderstanding of the implications of mathematical rigor;
*attempts to circumvent the usual criteria for publication of mathematical papers in a learned journal after peer review, often in the belief that the journal is biased against the author;
*lack of familiarity with, and therefore underestimation of, the existing literature.

Like astronomy, mathematics owes much to List of amateur mathematicians|amateur contributors such as Pierre de Fermat|Fermat and Marin Mersenne|Mersenne.-->
";

EnglishLetterFrequencies=LetterFrequencies[ToLetterCode[EnglishSampleText],26];
EnglishDigramFrequencies=DigramFrequencies[ToLetterCode[EnglishSampleText],26];

Here are all the letter frequencies:

Transpose[{Table[FromCharacterCode[i+65],{i,0,25}],EnglishLetterFrequencies *100}] //TableForm

Here are the five most common digrams:

f=Reverse[Ordering[EnglishDigramFrequencies, -5]];
Table[c=f[[i]];{FromCharacterCode[{Mod[c-1,26],Quotient[c-1,26]}+65],EnglishDigramFrequencies[[c]]*100},{i,Length[f]}] //TableForm

EnglishCharacterFrequencies=LetterFrequencies[ToCharacterCode[EnglishSampleText],256];

Clear[f,c]

Monoalphabetic ciphers

Caesar cipher

Caesar[x_Integer,k_]:=Mod[x+k,26];Caesar[x_String,k_]:=FromLetterCode[Caesar[ToLetterCode[x],k]];
SetAttributes[Caesar,Listable];

CaesarInv[x_,k_Integer]:=Caesar[x,-k];

Encode

Caesar["ALEAIACTAEST",3]

Decode

CaesarInv[%,3]

ROT13

ROT13[x_]:=Caesar[x,13]

Note that ROT13 is its own inverse:

Nest[ROT13,"ABCDEFGHIJKLMNOPQRSTUVWXYZ",2]

Affine cipher

Affine[x_Integer,{k1_Integer,k2_Integer}]:=Mod[k1 x+k2,26];
Affine[x_List,{k1_Integer,k2_Integer}]:=Mod[k1 x+k2,26];
Affine[x_String,{k1_Integer,k2_Integer}]:=FromLetterCode[Affine[ToLetterCode[x],{k1,k2}]];

AffineInv[x_,{k1_Integer,k2_Integer}]:=Affine[x,PowerMod[k1,-1,26]{1,-k2}];

Encode

Affine["ALEAIACTAEST",{3,4}]

Decode

AffineInv[%,{3,4}]

Xor cipher

XorCipher[x_Integer,k_Integer]:=BitXor[x,k];
XorCipher[x_String,k_Integer]:=BitXor[ToCharacterCode[x],k];
SetAttributes[XorCipher,Listable];

XorCipherInv[x_,k_]:=XorCipher[x,k];

Encode

XorCipher["ALEAIACTAEST",33]

We do not convert the output to a string, since not all printable characters are necessarily mapped to printable characters.

Decode

XorCipherInv[%,33] //FromCharacterCode

We could encode to base64 using

BaseEncode[ByteArray[%%]]

and back

Normal[ BaseDecode[%]]

How to crack monoalphabetic ciphers

The algorithm

We can crack any monoalphabetic cipher on a natural language by looking at letter frequencies. For every possible key we compare the letter frequencies of the decoded text with the expected letter frequencies and minimize the quadratic difference.

MonoCrack[x_List,Cipher_Symbol,NumKeys_Integer, LetterFreq_List]:=Module[{ma,l,lf, d,d0=2,k0=0},
l=Length[LetterFreq];
ma=Table[i,{i,0,l-1}];
lf=LetterFrequencies[x,l];
Do[
d=Part[lf,Cipher[ma,k]+1 ]-LetterFreq;
d=d.d;
If [d<d0,k0=k;d0=d],
{k,0,NumKeys-1}];
k0
];
MonoCrack[x_String,y__]:=MonoCrack[ToLetterCode[x],y];

Caesar cipher

ciphertext=Caesar["DIESERTEXTISTGEHEIM",3]

key=MonoCrack[%,Caesar,26, GermanLetterFrequencies]

CaesarInv[ciphertext,key]

Affine cipher

These are the admissible values for the first key

Z26s=Select[Table[i,{i,25}],(GCD[26,#]==1)&]

We encode the two keys as one.

Affine[x_,k_Integer]:=Affine[x,{Z26s[[Quotient[k,26]+1]],Mod[k,26]}];AffineInv[x_,k_Integer]:=AffineInv[x,{Z26s[[Quotient[k,26]+1]],Mod[k,26]}];

ciphertext=Affine["DIESERTEXTISTGEHEIM",26*1+4]

key=MonoCrack[ciphertext,Affine,26*12, GermanLetterFrequencies]

AffineInv[ciphertext,key]

Xor cipher

ciphertext=XorCipher["Dieser Text ist geheim.",77]

key=MonoCrack[ciphertext,XorCipher,256, GermanCharacterFrequencies]

XorCipherInv[ciphertext,key] //FromCharacterCode

Ployalphabetic ciphers

Vigenere cipher

Now the key is a list of keys which are used one after the other (cyclically) to encode each respective letter using a given monoalphabetic cipher.

Vigenere[x_List,k_List,Cipher_Symbol]:= Module[{ l=Length[k], y= {}},
Do[
y=Append[y,Cipher[x[[i]] ,k[[Mod[i-1,l]+1]]]],
{i,Length[x]}];
y
];
Vigenere[x_String,k_String,Caesar]:=FromLetterCode[Vigenere[ToLetterCode[x],ToLetterCode[k],Caesar]];
Vigenere[x_String,k_String,XorCipher]:=Vigenere[ToCharacterCode[x],ToCharacterCode[k],XorCipher];

The original Vigenere cipher uses the Caesar cipher.

Vigenere["ALEAIACTAEST","CAESAR",Caesar]

Many software developers use Vigenere with bitwise xor, since to them xor is more familiar than modular arithmetic .

Vigenere["ALEAIACTAEST","CAESAR",XorCipher]

This is also known as WPA (Weakest Possible Algorithm). See the next section why;-)

How to crack Vigenere

The algorithm

Vigenere can be cracked by looking at the letter coincidence index of the cipher text.

LetterCoincidence[x_List,m_Integer]:=Module[{l=Length[x],diff},
diff=x-RotateLeft[x,m];
(1/l)Sum[If[diff[[i]]==0,1,0],{i,l}]//N
];
LetterCoincidence[x_String,m_]:=LetterCoincidence[ToLetterCode[x],m];

Local maxima should occur at multiples of the key length. The following functions finds all indices above a given value kappa up to a maximum key length and tests if they are all a multiple of the first one found.

VigKeyLength[x_]:=Module[{kappa=0.055,maxkey=64,k={},i=0},
While[i≤ maxkey && Length[k]<3,
i++;
If[LetterCoincidence[x,i]>kappa,k=Append[k,i]]
];
If[Length[k]>2&& (k /. List->GCD)==k[[1]],k[[1]],Print["Sorry"]]
]

Once we know the key length,we can split the cipher text into parts which have been encoded with the same monoalphabetic cipher and crack each part separately.

SplitText[x_List,n_Integer]:=Module[{i,t},
t=Table[{},{i,n}];
Do[t[[Mod[i-1,n]+1]]=Append[ t[[Mod[i-1,n]+1]] ,x[[i]] ],{i,Length[x]}];
t
];
SplitText[x_String,n_]:=FromLetterCode[SplitText[ToLetterCode[x],n]];

Vigenere with Caesar cipher

We begin with a sample cipher text.

EnglishSampleText="Hello everybody out there using minix -
I'm doing a (free) operating system (just a hobby, won't be big and
professional like gnu) for threeeightysix (foureightysix) AT clones. This has
been brewing since april, and is starting to get ready. I'd like any feedback
on things people like/dislike in minix, as my OS resembles it somewhat
(same physical layout of the file-system (due to practical reasons)
among other things). I've currently ported bash(1.08) and gcc(1.40),and
things seem to work.This implies that I'll get something practical within a
few months, and I'd like to know what features most people would want. Any
suggestions are welcome, but I won't promise I'll implement them :-)
Linus (torvalds at kruuna.helsinki.fi)
PS. Yes - it's free of any minix code, and it has a multi-threaded fs.
It is NOT protable (uses threeeightysix task switching etc), and it probably never
will support anything other than AT-harddisks, as that's
all I have :-(.";

ciphertext=Vigenere[EnglishSampleText,"LINUX",Caesar];

To determine the key length, let us look for the letter coincidence index for key lengths up to 25

lc=Table[LetterCoincidence[ciphertext,m],{m,25}]

It looks like the local maxima occur at multiples of 5:

ListPlot[lc,PlotStyle->{PointSize[0.02`]},PlotRange->{0,0.1`}]

So we expect this to be the key length:

kl=VigKeyLength[ciphertext]

Now that we know the key length, we can split the cipher text into corresponding parts and crack each Caesar cipher:

MonoCrack[#,Caesar,26, EnglishLetterFrequencies]& /@ SplitText[ciphertext,kl] //FromLetterCode

Vigenere with Xor cipher

This works with our Xor cipher as well

ciphertext=Vigenere[EnglishSampleText,"LINUX",XorCipher];

lc=Table[LetterCoincidence[ciphertext,m],{m,25}]

ListPlot[lc,PlotStyle->{PointSize[0.02`]},PlotRange->{0,0.1`}]

Again, note that the maxima appear at multiples of 5:

kl=VigKeyLength[ciphertext]

Now that we have the key length, split the text and crack the individual parts:

MonoCrack[#,XorCipher,256, EnglishCharacterFrequencies]& /@ SplitText[ciphertext,kl] //FromCharacterCode

FromCharacterCode[Vigenere[ciphertext,ToCharacterCode[%],XorCipher]]

S-DES

S-DES

This is a simplified version of the DES algorithm operating on 8 bit blocks from Schaefer, E. (1996) A Simplified Data Encryption Standard Algorithm. Cryptologia, 20, 77-84. 
https://doi.org/10.1080/0161-119691884799

This function splits a 10 bit key into 8 bit subkeys for each round.

KeyGen[k_,s_]:=Module[{kk,key={},i},
kk=Part[IntegerDigits[k,2,10],{3,5,2,7,4,10,1,9,8,6}];
Do[
kk=Join[RotateLeft[Take[kk,5],s[[i]] ],RotateLeft[Take[kk,-5],s[[i]] ]];
key=Append[key,Part[kk,{6,3,7,4,8,5,10,9}]];
,{i,Length[s]}];
key]

The initial permutation and its inverse.

IP[x_]:=Part[x,{2,6,3,1,4,8,5,7}];
IPinv[x_]:=Part[x,{4,1,3,5,7,2,8,6}];

The Feistl function

F[x_,k_]:=Join[Mod[Take[x,4]+fBox[Take[x,-4],k],2],Take[x,-4]];
Theta[x_]:=Join[Take[x,-4],Take[x,4]];

The nonlinear part consisting of an initial expansion permutation, the S-Box (a nonlinear function given as a look-up table) and a final permutation.

fBox[x_,k_]:=Module[{y,yy},
y=Mod[Part[x,{4,1,2,3,2,3,4,1}]+k,2];
yy=(FromDigits[#,2]& /@Partition[Part[y,{1,4,2,3,5,8,6,7}],2])+1;
yy=IntegerDigits[4S[1][[ yy[[1]],yy[[2]] ]]+ S[2][[ yy[[3]],yy[[4]] ]],2,4];
Part[yy,{2,4,3,1}]
];
S[1]=(({{1, 0, 3, 2}, {3, 2, 1, 0}, {0, 2, 1, 3}, {3, 1, 3, 2}}));S[2]=(({{0, 1, 2, 3}, {2, 0, 1, 3}, {3, 0, 1, 0}, {2, 1, 0, 3}}));

Putting it all together we get our simplified version of DES:

SDES[x_Integer,k_Integer]:=Module[{xx,y,k1,k2},
{k1,k2}=KeyGen[k,{1,2}];
xx=IntegerDigits[x,2,8];
y=IPinv[F[Theta[F[IP[xx],k1]],k2]];
FromDigits[y,2]
];
SDESInv[x_Integer,k_Integer]:=Module[{xx,y,k1,k2},
{k1,k2}=KeyGen[k,{1,2}];
xx=IntegerDigits[x,2,8];
y=IPinv[F[Theta[F[IP[xx],k2]],k1]];
FromDigits[y,2]
];
SetAttributes[{SDES,SDESInv},Listable];

SDES[{0,1,2},34]

SDESInv[%,34]

Note that even though the input bytes differ by only one byte, the output bytes differ by about 50% of the bits!

tmp=IntegerDigits[%%,2,8]

BitXor[tmp[[1]],tmp[[2]]] /.List->Plus

BitXor[tmp[[1]],tmp[[3]]]/.List->Plus

BitXor[tmp[[2]],tmp[[3]]]/.List->Plus

The S-box as a polynomial

Here are the two functions f[j,x] defined by the matrices S[j]

f[x_Integer,j_Integer]:=Module[{y},
y=IntegerDigits[x,2,4];
y=(FromDigits[#,2]& /@Partition[Part[y,{1,4,2,3}],2])+1;
y=IntegerDigits[S[j][[ y[[1]],y[[2]] ]],2,2];
y
];

Let abcd be the four input bits

x={a,b,c,d};

Then the two functions are given by the following polynomials

Do[dig=IntegerDigits[i,2,4];
min[i]=1;
Do[
min[i]=If[dig[[j]]==1,min[i] x[[j]],min[i]*(1+x[[j]])],{j,4}];
,{i,0,15}];

p[1]=Expand[Sum[f[i,1]min[i] ,{i,0,15}] ]/. a_^n_ -> a /. n_Integer -> Mod[n,2]

p[2]=Expand[Sum[f[i,2]min[i] ,{i,0,15}] ]/. a_^n_ -> a /. n_Integer -> Mod[n,2]

Let us verify this

Table[Table[{a,b,c,d}=IntegerDigits[i,2,4];
f[i,j]==Mod[p[j],2]
,{i,0,15}]/. List->And,{j,2}]

Clear[a,b,c,d,f,p,x,dig,min]

Statistical properties of S-DES

The dependency matrix of a nonlinear function F from n bits to m bits tells us the probability of a change of output bits with respect to a change of input bits

DependencyMatrix[myF_,n_,m_]:=Block[{y=Table[0,(2^n)],myA=Table[0,n,m]},
Do[y[[x]]=myF[x-1];,{x,(2^n)}];
Do[Do[
If[BitAnd[(2^(j-1)),y[[x+1]]]=!=BitAnd[(2^(j-1)),y[[BitXor[x,(2^(i-1))]+1]]],myA[[n-i+1,m-j+1]]++],{i,n},{j,m}]
,{x,0,(2^n)-1}];
(1/(2^n))myA
];
DependencyMatrix[myG_,n_]:=Block[{myF,m},
m=Length[myG[Table[0,n]]];
myF=FromDigits[myG[IntegerDigits[#,2,n]],2]&;
DependencyMatrix[myF,n,m]
];

Here is the dependency matrix for S-DES:

N[DependencyMatrix[SDES[#,0]&,8,8],2]//MatrixForm

This does not look to good! All entries should be roughly 1/2 (avalanche criterion). The problem is that we only have two rounds. If we increase the number of rounds to 4, it will look much better:

SDES[x_,k_,n_]:=Module[{xx,key},
key=KeyGen[k,Table[j,{j,n}]];
xx=IP[IntegerDigits[x,2,8]];
Do[xx=Theta[F[xx,key[[j]]]],{j,n}];
FromDigits[IPinv[Theta[xx]],2]
];

N[DependencyMatrix[SDES[#,0,4]&,8,8],2]//MatrixForm

Operation modes

ECB[x_List,k_]:=SDES[x,k];
CBC[x_List,k_,iv_]:=Module[{y={iv},l=Length[x]},Do[y=Append[y,SDES[BitXor[x[[i]],y[[i]]],k]],{i,l}];
y];
CFB[x_List,k_,iv_]:=Module[{y={iv},l=Length[x]},Do[y=Append[y,BitXor[SDES[y[[i]],k],x[[i]]]],{i,l}];
y];
OFB[x_List,k_,iv_]:=Module[{z=iv,y={iv},l=Length[x]},Do[z=SDES[z,k];
y=Append[y,BitXor[z,x[[i]]]],{i,l}];
y];

msg=ToCharacterCode["FAD"]

ECB[msg,244]

CBC[msg,244,0]

CFB[msg,244,0]

OFB[msg,244,0]

S-Crypt

Pasword hashing with a salt based on S-DES inspired by the UNIX crypt function:

SCrypt[s_,p_]:=Nest[SDES[#,s+4 p]&,0,5]

SCrypt[2,9]

How to crack S-DES (the naive way)

It is easy to crack the f-box of S-DES by following the input/output forward/backwards and then check the resulting keys if they are compatible with the key generation from S-DES. Since there are just two rounds, this is all we need!

fBoxCrack[x_,y_]:=Block[{tmp={},xx,xl,xr,yy,yl,yr,id,kl={},kr={}},
xx=EBox[x];yy=PBoxinv[y];
xl=Take[xx,4];xr=Take[xx,-4];
yl=Take[yy,2];yr=Take[yy,-2];
Do[id=IntegerDigits[i,2,4];
If[SBox1[id]==yl,kl=Append[kl,BitXor[id,xl]]];
If[SBox2[id]==yr,kr=Append[kr,BitXor[id,xr]]];
,{i,0,15}];
Flatten[Table[Join[kl[[j]],kr[[k]]],{j,Length[kl]},{k,Length[kr]}],1]
];
FindCompatibleKeys[pk1_,pk2_]:=Block[{tmp={},kt1,kt2},
Do[
kt1=pk1[[j]];kt2=pk2[[k]];
If[And[kt1[[1]]==kt2[[8]],kt1[[6]]==kt2[[2]],kt1[[8]]==kt2[[3]],kt1[[5]]==kt2[[1]],kt1[[3]]==kt2[[7]],kt1[[7]]==kt2[[5]]],tmp=Append[tmp,{kt1[[1]],kt2[[6]],kt1[[6]],kt1[[4]],kt2[[4]],kt1[[8]],kt1[[2]],kt1[[5]],kt1[[3]],kt1[[7]]}]];
,{j,Length[pk1]},{k,Length[pk2]}];
FromDigits[#,2]& /@tmp];
SDESCrack[x_,y_]:=Block[{xd,l,r,yd,ll,rr,f1,f2},
xd=IP[IntegerDigits[x,2,8]];
yd=IP[IntegerDigits[y,2,8]];
{l,r}={Take[xd,4],Take[xd,-4]};
{ll,rr}={Take[yd,4],Take[yd,-4]};
{f1,f2}={BitXor[rr,l],BitXor[ll,r]};
FindCompatibleKeys[fBoxCrack[r,f1],fBoxCrack[BitXor[l,f1],f2]]
];

Let us take a pair of plain and cipher text:

x=229;k=258;y=SDES[x,k]

Let' us crack  S-DES

Timing[SDESCrack[x,y]]

All keys found work:

SDES[x,#]& /@ %[[2]]

And it is faster than brute-force:

Timing[tmp={};Do[If[SDES[x,i]==y,tmp=Append[tmp,i]],{i,0,(2^10)-1}]; tmp]

More advanced techniques like linear or differential cryptanalysis are needed if the number of rounds is increased.

Public key ciphers

DLP/Elgamal

The DLP is the problem of inverting the discrete exponential function (modulo a prime p)

p=47;a=3;
ListPlot[Table[{x,PowerMod[a,x,p]},{x,0,p-1}],PlotLabel->Mod[(a^x),p]]

Of course this can be done by trying all possibilities

LogMod[a_,b_,p_]:=Block[{j=0},
While[PowerMod[a,j,p]!=b&&j<p,j++];
If[j<p,j,Print["Warning! ",b," is not a power of ",a, " modulo ",p];Null]];

LogMod[a,6,p]

PowerMod[a,%,p]

There is also a built-in command:

MultiplicativeOrder[a,p,{6}]

The Diffie - Hellman key exchange:

We start by selecting a prime such that p-1 has a large prime order:

p=1283;q=((p-1)/2);g=3;PrimeQ[{p,q}]

In this case the big prime factor q is maximal (such p are called safe primes). Let us make sure that the order of g is indeed q:

MultiplicativeOrder[g,p]==q

Hence (g^a)will always have the order q no matter what we choose for a. Now Alice and Bob both choose their respective secrets

{a,b}=RandomInteger[{2,q-1},2]

and exchange the corresponding public quantities

{α,β}=PowerMod[g,{a,b},p]

Now both have a common shared secret given by

{PowerMod[α,b,p],PowerMod[β,a,p]}

If Eve, who only knows α and β, wants to know the secret, she needs to compute the discrete log

LogMod[g,α,p]

to obtain the secret key of Alice, say. If q is big, this is computationally infeasible.

Generate random parameters for the DH key exchange

SeedRandom[Method->"OpenSSL"];
MyRandomPrime[l_Integer]:=RandomPrime[{Ceiling[(Sqrt[2]) (2^(l-1))],(2^l)-1}];

DHParamters[l_Integer]:=Module[{p,q,r=2,h=2},
q=MyRandomPrime[l];
While[!PrimeQ[q r+1],r+=2];
p=q r+1;
While[PowerMod[h,r,p]==1,h=RandomInteger[{2,p-2}]];
{p,q,PowerMod[h,r,p]}];

{p,q,g}=DHParamters[128]

RSA

Factoring integers is much harder than multiplying them:

Timing[999999599*9999999967]

Timing[FactorInteger[%[[2]]]]

The RSA algorithm

This is the public key

n= 1147; e=29;

Note that n is the product of two primes

FactorInteger[n]

One can either use the Carmichael function λ or Euler’s ϕ function:

{CarmichaelLambda[n],EulerPhi[n] }

In this case it will lead to the same private key

d=PowerMod[e,-1,CarmichaelLambda[n]]

Now we can encrypt:

x=ToCharacterCode["FAD"]-65

y=PowerMod[x,e,n]

and decrypt:

PowerMod[y,d,n]

Encrypt x with a given key (n,e):

RSA[x_Integer,{n_Integer,e_Integer}]:=PowerMod[x,e,n]/;x<n;
RSA[x_List,{n_Integer,e_Integer}]:=RSA[#,{n,e}]&/@ x;

Convert a string to blocks of size < n and back:

StringToBlocks[x_String,n_Integer]:=IntegerDigits[FromDigits[ToCharacterCode[x],128],n];
BlocksToString[x_List,n_Integer]:=FromCharacterCode[IntegerDigits[FromDigits[x,n],128]];

x=StringToBlocks["SQUEAMISH OSSIFRAGE",n]

y=RSA[x,{n,e}]

x=RSA[y,{n,d}]

BlocksToString[x,n]

To obtain the private key d from the public key e, one needs to compute

EulerPhi[n]

For this one needs to factor n, which is computationally infeasible if both prime factors are sufficiently big.

Note that RSA should always be used with secure padding. For this we need a cryptographic hash function. We choose a very simple one which provides no
security (apart from the fact, that our modulus and block size are too small)!

RSAOAEP[x_,{n_,e_}]:=Block[{k=8,k0,X,Y,r,H},
If [(k0=Floor[Log[2,n]]-k)<=0,Return[Print["Error: n needs to be at least",(2^(k+1)), "!"];$Failed,Block]];
If [!(0<= x < 2^k),Return[Print["Error: x can be at most ",(2^k), "!"],Block];$Failed];
H[h_,j_]:=Mod[PowerMod[h,2,n],(2^j)];
r=RandomInteger[(2^k0)-1];
X=BitXor[x,H[r,k]];Y=BitXor[r,H[X,k0]];
PowerMod[(2^k0)X+Y,e,n]
];
RSAOAEP[x_List,{n_Integer,d_Integer}]:=RSAOAEP[#,{n,e}]&/@ x;
RSAOAEPinv[y_,{n_,d_}]:=Block[{k=8,k0,X,Y,r,H},
If [(k0=Floor[Log[2,n]]-k)<=0,Return[Print["Error: n needs to be at least",(2^(k+1)), "!"];$Failed,Block]];
If [!(0<= y < n),Return[Print["Error: y can be at most ",n, "!"];$Failed,Block]];
H[h_,j_]:=Mod[PowerMod[h,2,n],(2^j)];
{X,Y}=QuotientRemainder[PowerMod[y,d,n],(2^k0)];
r=BitXor[Y,H[X,k0]];
BitXor[X,H[r,k]]
];
RSAOAEPinv[x_List,{n_Integer,d_Integer}]:=RSAOAEPinv[#,{n,d}]&/@ x;

Our message is

x=ToCharacterCode["SQUEAMISH OSSIFRAGE"];

The encrypted message is

y=RSAOAEP[x,{n,e}]

Decrypting gives back our original message

RSAOAEPinv[y,{n,d}]//FromCharacterCode

Generate a random prime with a given number of bits

SeedRandom[Method->"OpenSSL"];
MyRandomPrime[l_Integer]:=RandomPrime[{Ceiling[(Sqrt[2]) (2^(l-1))],(2^l)-1}];

Generate (pseudorandom) keys (n,e) and (n,d) given e and a required number of binary digits l for n (cf. https://doi.org/10.6028/NIST.FIPS.186-5):

RSAKeys[e_Integer,l_Integer]:=Block[{found=False,p,q,d,l2=Ceiling[l/2]},
If[l2<2048,Print["Warning: l too small."];If[l2<=6,l2=6]];
If[EvenQ[e],Print["Warning: e even."];e++];
If[e<=(2^16),Print["Warning: e too small."]];
If[e>=(2^256),Print["Warning: e too large."]];
If[d<=(n^(1/3)),Print["Warning: d too small."]]; (* Wiener attack *)
While[!found,
p=MyRandomPrime[l2];
q=MyRandomPrime[l2];
found=And[Abs[p-q]>(2^(l2-100)),GCD[p-1,e]==1,GCD[q-1,e]==1];
If [found,d=PowerMod[e,-1,LCM[p-1,q-1]];found=(d>(2^l2))];
];
(* Print["{p,q}=",{p,q}]; *)
{{p q,e},{p q,d}}];

FermatNumber[k_]=(2^(2^k))+1;

RSAKeys[FermatNumber[0],12]

Clear[p,q,n,e,d]

Safe/Strong Primes

Test if a prime is safe/generate a random safe prime

SafePrimeQ[p_Integer]:=PrimeQ[p]&&PrimeQ[((p-1)/2)];
RandomSafePrime[l_Integer]:=Module[{p},p=RandomInteger[{(2^(l-1)),(2^l)-1}];
p=p-Mod[p,12]+11;(* Use -Mod[p,24]+23 and step size 24 if g=2 should have order (p-1)/2 *)
While[!(SafePrimeQ[p]),p+=12];
p];

Generate a strong  prime using Gordan’s algorithm

RandomGordonPrime[l_]:=Block[{s=RandomPrime[{(2^(l-1)),(2^l)-1}],t=RandomPrime[{(2^(l-1)),(2^l)-1}],r,i,u,uu},
Print["s: ", s];
Print["t: ", t];
u=2t;uu=u*RandomInteger[1,100];
i=0;While[i<1000&&!PrimeQ[uu+1],uu=uu+u;i++];
r=uu+1;
If[i==1000,Return[0],Print["r: ",r," found after ",i, " steps."];];
u=2r s;uu=u*RandomInteger[1,100]+2s PowerMod[s,r-2,r]-1;
i=0;While[i<1000&&!PrimeQ[uu],uu=uu+u;i++];
If[i==1000,Return[0],Print["p found after ",i, " steps."]];
uu]

RandomGordonPrime[256]

Note that strong prime are no longer necessary for RSA, since the provide only negligible advantages given current factorization algorithms.

Elliptic Curves

EC over R

Neg[{x_,y_},{a_,b_}]:={x,-y};
Add[{x1_,y1_},{x2_,y2_},{a_,b_}]:=Which[{x1,y1}=={∞,∞},{x2,y2},{x2,y2}=={∞,∞},{x1,y1},x1==x2&&y1==-y2,{∞,∞},x1==x2&&y1==y2,Block[{s=(((3(x1^2)+a)/(2y1)))},{(s^2)-x1-x2,s(x1-(s^2)+x1+x2)-y1}],True,Block[{s=(((y2-y1)/(x2-x1)))},{(s^2)-x1-x2,s(x1-(s^2)+x1+x2)-y1}]];
Add[{x1_,y1_},{x2_,y2_},P__,{a_,b_}]:=Add[Add[{x1,y1},{x2,y2},{a,b}],P,{a,b}];
Mult[0,{x1_,y1_},{a_,b_}]:={∞,∞};
Mult[n_,{x1_,y1_},{a_,b_}]:=Mult[-n,{x1,-y1},{a,b}]/; n<0;
Mult[n_,{x1_,y1_},{a_,b_}]:=Add[{x1,y1},Mult[n-1,{x1,y1},{a,b}],{a,b}]/; n>0 &&OddQ[n];
Mult[n_,{x1_,y1_},{a_,b_}]:=Mult[n/2,Add[{x1,y1},{x1,y1},{a,b}],{a,b}]/; n>0 &&EvenQ[n];

Mult[2,{0,2},{-2,4}]

Add[{0,2},{3,5},{-2,4}]

Solve[(x^(3 ))-6x+7==0,x]//N

Manipulate[
y1= sig1(Sqrt[(x1^(3 ))+a x1+b]);
y2= sig2(Sqrt[(x2^(3 ))+a x2+b]);
s=If[x1==x2,((3x1+a)/(2y1)),((y2-y1)/(x2-x1))];
x3=Simplify[(s^2)-x1-x2];
y3=Simplify[y1+s (x3-x1)];
mylable={"P","Q","R","(SuperStar[R])"};
pts={{x1,y1},{x2,y2},{x3,y3},{x3,-y3}};
p1=ContourPlot[y==y1+s(x-x1),{x,-3,4},{y,-6,6},Epilog->{PointSize[0.02],Black,Point[#]&/@pts,Black,Table[Text[mylable[[j]],pts[[j]]+{0,0.3}],{j,4}]}];
Show[p1,p2],{{x1,2},-2.9,4},{sig1,{+1,-1},Checkbox},{{x2,0},-2.9,4},{sig2,{+1,-1},Checkbox},Initialization:>{a=-6;b=7;p2=ContourPlot[(y^2)==(x^(3 ))-6x+7,{x,-3,4},{y,-6,6},ContourStyle->Black]}]

ContourPlot[y^2==x^3-2x+4, {x, -3, 3},{y, -6,6}]

Proof of the associative law:

Clear[x1,x2,x3,y1,y2,y3,a,b,s]

Add[{x1_,y1_},{x2_,y2_}]:=Block[{s=(((y2-y1)/(x2-x1)))},{(s^2)-x1-x2,s(x1-(s^2)+x1+x2)-y1}];

Simplify[Simplify[Factor[Add[Add[{x1,y1},{x2,y2}],{x3,y3}][[1]]-Add[{x1,y1},Add[{x2,y2},{x3,y3}]][[1]]]]/.{(y1^2)->(x1^3)+a x1 +b,(y2^2)->(x2^3)+a x2 +b,(y3^2)->(x3^3)+a x3 +b}]

Simplify[Simplify[Factor[Add[Add[{x1,y1},{x2,y2}],{x3,y3}][[2]]-Add[{x1,y1},Add[{x2,y2},{x3,y3}]][[2]]]]/.{(y1^2)->(x1^3)+a x1 +b,(y2^2)->(x2^3)+a x2 +b,(y3^2)->(x3^3)+a x3 +b}]

EC over (Subscript[Z, p])

Compute a root in (Subscript[Z, p]):

PowerMod[14,(1/2),11]

The second root is

Mod[-%,11]

Not every number is a square

PowerMod[2,(1/2),11]

This can be checked using the Jacobi symbol:

{JacobiSymbol[2,11],JacobiSymbol[0,11],JacobiSymbol[14,11]}

EllipticCurve[{a_,b_,p_}]:=Block[{tmp={{∞,∞}},Δ=Mod[(4(a^3)+27 (b^2)),p],y2,y},
Print["Δ=",Mod[Δ,p],If[Δ==0," Singular!",""]];
Do[
y2=Mod[x((x^2)+a ) +b,p];
If[y2==0,tmp=Append[tmp,{x,0}],
If[JacobiSymbol[y2,p]==1,y=PowerMod[y2,(1/2),p];tmp=Append[tmp,{x,y}];tmp=Append[tmp,{x,Mod[-y,p]}]]
]
,{x,0,p-1}];
Print["Order=",Length[tmp]];
tmp
];
OnCurveQ[{x_,y_},{a_,b_,p_}]:=If[{x,y}=={∞,∞},True,Mod[(y^2)-x((x^2)+a ) -b,p]==0];
Neg[{x_,y_},{a_,b_,p_}]:={x,Mod[-y,p]};
Add[{x1_,y1_},{x2_,y2_},{a_,b_,p_}]:=Which[{x1,y1}=={∞,∞},{x2,y2},{x2,y2}=={∞,∞},{x1,y1},Mod[x1-x2,p]==0&&Mod[y1+y2,p]==0,{∞,∞},Mod[x1-x2,p]==0&&Mod[y1-y2,p]==0,Block[{s=Mod[(3(x1^2)+a)PowerMod[2y1,-1,p],p]},Mod[{(s^2)-x1-x2,s(x1-(s^2)+x1+x2)-y1},p]],True,Block[{s=Mod[(y2-y1)PowerMod[x2-x1,-1,p],p]},Mod[{(s^2)-x1-x2,s(x1-(s^2)+x1+x2)-y1},p]]];
Add[{x1_,y1_},{x2_,y2_},P__,{a_,b_,p_}]:=Add[Add[{x1,y1},{x2,y2},{a,b,p}],P,{a,b,p}];
Mult[0,{x1_,y1_},{a_,b_,p_}]:={∞,∞};
Mult[n_,{x1_,y1_},{a_,b_,p_}]:=Mult[-n,{x1,Mod[-y1,p]},{a,b,p}]/; n<0;
Mult[n_,{x1_,y1_},{a_,b_,p_}]:=Add[{x1,y1},Mult[n-1,{x1,y1},{a,b,p}],{a,b,p}]/; n>0 &&OddQ[n];
Mult[n_,{x1_,y1_},{a_,b_,p_}]:=Mult[n/2,Add[{x1,y1},{x1,y1},{a,b,p}],{a,b,p}]/; n>0 &&EvenQ[n];
EllipticCurveOrder[{a_,b_,p_}]:=p+1+(∑_(x=0)^(p-1))JacobiSymbol[(x^3)+a x +b,p];
EllipticOrder[{x_,y_},{a_,b_,p_}]:=Block[{xx=x,yy=y,j=1},While[{xx,yy}!={∞,∞},j++;{xx,yy}=Add[{x,y},{xx,yy},{a,b,p}]];j];

parm={-3,1,11};

ec=EllipticCurve[parm]

Table[Mult[n,{0,1},parm],{n,1,16}]

OnCurveQ[{4,9},parm]

Add[{4,9},{4,9},parm]

EllipticOrder[{4,9},parm]

Add[{4,3},{4,9},parm]

Create a Cayley table

Table[Add[ec[[i]],ec[[j]],parm],{i,Length[ec]},{j,Length[ec]}]//MatrixForm

Check associativity (Light’s associativity test)

tmp=True;Do[If[i<=j<=k,tmp=And[tmp,Add[ec[[i]],ec[[j]],ec[[k]],parm]==Add[ec[[i]],ec[[k]],ec[[j]],parm]]],{i,Length[ec]},{j,Length[ec]},{k,Length[ec]}];tmp

Add[{1,9},{1,9},{6,9},parm]

Add[{1,9},{1,9},{1,9},parm]

Mult[3,{1,9},parm]

Prameters[{x1_,y1_},{x2_,y2_},p_]:=Block[{},
Solve[{(x1^3)+ a x1+b==(y1^2),(x2^3)+ a x2+b==(y2^2)},{a,b},Modulus->p]];

Prameters[{1,9},{1,2},11]

NIST P-192

G={602046282375688656758213480587526111916698976636884684818,174050332293622031404857552280219410364023488927386650641};
a=-3;b=2455155546008943817740293915197451784769108058161191238065;p=6277101735386680763835789423207666416083908700390324961279;
parm={a,b,p};
n=6277101735386680763835789423176059013767194773182842284081;

PrimeQ[n]

Mod[((G[[2]])^2)-((G[[1]])^3)-a G[[1]]-b,p]==0

k=RandomInteger[p-1]

P=Mult[k,G,parm]

secp256k1 (Bitcoin)

G={55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424};
a=0;b=7;p=115792089237316195423570985008687907853269984665640564039457584007908834671663;
parm={a,b,p};
n=115792089237316195423570985008687907852837564279074904382605163141518161494337;

Mod[((G[[2]])^2)-((G[[1]])^3)-a G[[1]]-b,p]==0

k=RandomInteger[p-1]

P=Mult[k,G,parm]

Classical ellipses over (Subscript[Z, p])

Note that you can also turn a classical ellipse into a group. To this end notice, that an ellipse is just a scaled unit circle

(x^2)+ (y^(2 ))==1/. {x->(x/a),y->(y/b)}

and the unit circle has a natural group structure if you identify points in the plane with complex numbers

(x1+I y1)(x2 + I y2) //ComplexExpand

This leads to the following group structure

Add[{x1_,y1_},{x2_,y2_},{a_,b_,p_}]:=Mod[{PowerMod[a,-1,p]x1 x2-a PowerMod[b,-2,p]y1 y2,PowerMod[a,-1,p](x2 y1+x1 y2)},p];
Neg[{x_,y_},{a_,b_,p_}]:=Mod[{x,-y},p];
OnCurveQ[{x_,y_},{a_,b_,p_}]:=(Mod[PowerMod[a,-2,p](x^2)+PowerMod[b,-2,p](y^2),p]==1);

Note that the neutral element is (a,0).

We can get all points using

Ellipse[{a_,b_,p_}]:=Block[{tmp={},y2,y},
	Do[
		y2=Mod[(b^2)(1-PowerMod[a,-2,p]x^2),p];
		If[y2==0,tmp=Append[tmp,{x,0}]];
		If[JacobiSymbol[y2,p]==1,y=PowerMod[y2,1/2,p];tmp=Append[tmp,{x,y}];tmp=Append[tmp,{x,Mod[-y,p]}]];
	,{x,0,p-1}];
	tmp];

Here is how it looks like

ListPlot[Ellipse[{3,4,101}]]

As you can see, the curve has a lot of structure and hence is unlikely to be useful for cryptography. Moreover, note that an ellipse is always isomorphic to the unit circle (after all, this is how we constructed it in the first place;-)

ListPlot[Ellipse[{1,1,101}]]