Cryptographic methods -Let's do the math - part 1 (DEU)

^Quelle

Wir bewegen uns alle im Kryptokosmos und sei es mindestens auf Hive. Wie der Begriff Kryptowährung schon vermuten lässt, haben Kryptowährungen mit kryptographischen Verfahren zu tun. Aber was für kryptographische Verfahren gibt es und was haben die mit Blockchain zu tun?

Eine Sache schon mal vorab, ich habe mich etwas mit dem Thema beschäftigt und werde es eher aus einer mathematischen Perspektive beleuchten und weniger aus der Sicht der Informatik.

Ich werde zwischen drei Prinzipien unterscheiden und auf einige Verfahren auch genauer eingehen.

1. Symmetrische Verfahren
2. Asymmetrische Verfahren
3. Einwegfunktionen

Asymmetrische Verfahren sind diejenigen Verfahren, die unter anderen in der Blockchainwelt benutzt werden. Auch Einwegfunktionen sind für Kryptofreaks relevant, da das sogenannte Hashen eine kryptographische Einwegfunktion ist. Ein weiterer Punkt sind digitale Signaturen. Auch die machen sich asymmetrische Verfahren zu nutze und da bei einer Blockchain zum Beispiel bei Hive Transaktionen digital signiert werden, werden wir das näher beleuchten.

Wir brauchen natürlich auch etwas Mathematik für die ganzen Verfahren. Deshalb gehen ich zuerst auf symmetrische Verfahren ein, damit wir ein Gefühl für die Mathematik, welche wir brauchen werden bekommen.

Symmetrische Verfahren

Auch heutzutage finden symmetrische Verschlüsselungsverfahren noch ihre Anwendung, da sie schneller gehen als asymmetrische Verschlüsselungsverfahren, zum Beispiel die End-Zu-End-Verschlüsselung von WhatsApp. (Genauer gesagt ist aber eine Kombination aus symmetrischer und asymmetrischer Verschlüsselung.)

Bevor wir aber richtig loslegen können, brauchen wir aber noch etwas Mathematik. In diese wollen wir aber nicht sehr tief reingehen - also keine Sorge.

Gruppen

Zuerst wollen wir klären was eine Gruppe ist. Also Grundlage haben wir eine Menge und eine Rechenoperation. Die Menge muss bezüglich der Rechenoperation abgeschlossen sein, d.h. jedes Rechenergebnis muss wieder innerhalb der Gruppe sein.

Haben wir zum Beispiel die Menge {1,2,3,4} und die Rechenoperation + wäre diese Menge nicht abgeschlossen. Zum Beispiel ist 3+4=7 und 7 ist nicht in unserer Menge. Die Menge der natürlichen Zahlen {1,2,3,4,5...} wäre hingegen bzgl. der Addition abgeschlossen.

Eine Menge G samt Rechenoperation o heißt Gruppe, falls folgende drei Axiome gelten:

1. Existenz eines neutralen Elements e
   aoe=a

2. Existenz eines inversen Elements a^-1
   aoa^-1=e

3. Assoziativgesetz
   (aob)oc=ao(boc)

Jetzt wollen wir das mal mit einem Beispiel füttern. Sind die ganzen Zahlen {0,1,-1,2,-2,3,-3...} eine Gruppe bzgl. +?

Diese Frage sollte nicht besonders schwer zu beantworten sein. Wir können ja schlicht die drei Axiome prüfen.

1. Gibt es a+e=a? Das neutrale Element wird wohl 0 sein. Denn a+0=a. D.h. 0 ist das neutrale Element der Addition. Wer sich schon mal gefragt hat, warum Mathematiker ständig nach der "Null" (Nullvektor, Nullmatrix etc.) suchen, hat hier die Antwort.

2. Natürlich gibt es zu a auch a^-1. Denn a+a^-1=a+(-a)=a-a=0. Das Inverse ist übrigens wichtig damit wir Gleichungen umformen können.

3. Auch dieses Gesetz gilt. Eine Begründung verklemme ich mir an diese Stelle. Inhaltlich sind nämlich die ersten beiden Axiome für uns die relevanten.

Wir sehen also, dass die ganzen Zahlen eine Gruppe bzgl. + sind. Sind sie auch eine Gruppe bzgl. der Multiplikation ^.?

1. Das neutrale Element wäre 1, da a^.1=a. Ähnlich der 0 suchen Mathematiker auch ständig nach der "1" (Einheitsmatrix, Identität etc.)

2. Leider finden wir kein Inverses in den ganzen Zahlen. So wäre 5^.5^-1=5^.(1/5)=1. 1/5 wäre aber keine ganze Zahl. Somit sind die ganzen Zahlen keine Gruppe bzgl. der Multiplikation. Es sei an dieser Stelle außerdem angemerkt, dass wir nachfolgend die "0" bei der Multiplikation nicht mit einbeziehen, da die "0" kein multiplikatives Inverses besitzt.

In der Kryptographie werden wir aber nicht klassisch addieren oder klassisch multiplizieren. Wir werden Modulo rechnen. Ich habe hier schon mal erklärt wie man Modulo rechnet.

Aber ich werde es nochmal kurz wiederholen. Modulo ist Teilen mit Rest, aber man rechnet nur mit dem Rest. Wir könnten zum Beispiel prüfen, ob der F₅={0,1,2,3,4} eine Gruppe bzgl. der Multiplikation ist. Stellt euch den F₅ als Menge vor in der man nur Modulo 5 rechnen darf.

So wäre 3+4=7=2 mod 5 und 3^.4=12=2 mod 5.

Wir könnten uns auch fragen was z.B. 4²⁰²¹ mod 5 ist.

Easy:

4²⁰²¹=(-1)²⁰²¹=-1=4 mod 5.

Aber zurück zur Frage ob es sich um eine Gruppe handelt:

1. Das neutrale Element ist einfach 1, wie sollte es auch anders sein.

2. Für die Frage nach dem Inversen wird es schon schwerer. Hat jedes Element unserer Menge ein Inverses? 1^.1=1 mod 5, 2^.3=6=1 mod 5, 3^.2=6=1 mod 5 und 4^.4=16=1 mod 5. Die 0 schließt man wie schon erwähnt bei der Multiplikation aus, da 0 kein Inverses besitzt.

3. Das Assoziativgesetz gilt auch aber das werden wir nicht prüfen.

Folglich gelten alle Axiome und es handelt sich um eine Gruppe.

Kommen wir zurück zur symmetrischen Verschlüsselung.

Caesar Verschlüsselung

Bei einer symmetrischen Verschlüsselung haben Sender und Empfänger beide den selben Schlüssel, was auch das Hauptproblem bei solchen Verfahren darstellt. Es muss nämlich dafür ein Schlüsseltausch stattfinden. Hier könnte ein Angreifer natürlich aktiv werden und versuchen an den Schlüssel zu kommen.

Die bekannteste Idee ist einfach das Alphabet um k stellen zu verschieben und so den Text zu verschlüsseln. Dies bezeichnen wir als additive Caesar-Verschlüsselung. Dafür ordnen wir jeden Buchstaben eine Zahl zu (A=0,B=1,C=2...).

Das Wort H I V E wäre 7 8 21 4. Ist jetzt unser Schlüssel k=5 müssen wir schlicht +5 mod 26 rechnen.

H I V E

7 8 21 4

12 13 0 9

M N A J

Diese Verschlüsselung wäre aber sehr leicht zu knacken, da wir nur 26 Möglichkeiten haben einen Schlüssel zu wählen.

Um das Ganze noch etwas aufzupeppen, könnten wir auch eine multiplikative Caesar-Verschlüsselung nutzen.

Nehmen wir als Schlüssel erneut k=5. 7^.5=35=9 mod 26, 8^.5=40=14 mod 26, 21^.5=105=1 mod 26 und 4^.5=20 mod 26.

H I V E

7 8 21 4

9 14 1 20

J O B U

Natürlich gibt es auch hier nur 26 Möglichkeiten einen Schlüssel zu nehmen. Und man sollte auch nicht unbedingt Zahlen wie 13 oder 2 nehmen. Aber wir könnten den Schlüsselraum deutlich erhöhen, wenn wir beide Varianten gleichzeitig machen.

Sei hierfür k₁=5 und k₂=3. Wir wollen mit y=x^.k₁+k₂ verschlüsseln. Und erneut soll das Wort HIVE verschlüsselt werden. Dann wollen wir mal:

y₁=7^.5+3=12 mod 26

y₂=8^.5+3=17 mod 26

y₃=21^.5+3=4 mod 26

y₄=4^.5+3=23 mod 26

H I V E

7 8 21 4

12 17 4 23

M Q E X

Aber wie wird das Ganze jetzt entschlüsselt? Ich habe ja schon mal erwähnt, dass das Inverse benötigt wird ,um Gleichungen umzustellen. D.h. wir müssen y=x^.k₁+k₂ nach x umstellen:

y=x^.k₁+k₂ |+k₂^-1

y+k₂^-1=x^.k₁+k₂+k₂^-1

y+k₂^-1=x^.k₁+0

y+k₂^-1=x^.k₁ |^.k₁^-1

(y+k₂^-1)^.k₁^-1=x^.k₁^.k₁^-1

(y+k₂^-1)^.k₁^-1=x^.1

x=(y+k₂^-1)^.k₁^-1

Hier rechnen wir natürlich steht Modulo 26.

Nun werden wir noch am Beispiel y₁ die Entschlüsselung vollziehen.

x₁=(y₁+k₂^-1)^.k₁^-1

x₁=(7+k₂^-1)^.k₁^-1

Wir brauchen also k₂^-1, was das additive Inverse zu k₂=3 ist, und k₁^-1, welches das multiplikative Inverse zu k₁=5 ist.

Fangen wir mit dem additiven Inversen an. Es gilt:

k₂+k₂^-1=0

In den ganzen Zahlen wäre k₂+k₂^-1=3+3^-1=3-3=0. Das können wir auch auf Modulo 26 übertragen. Denn -3=23 mod 26. Folglich gilt:

k₂+k₂^-1=3+k₂^-1=3-3=3+23=0 mod 26

Das multiplikative Inverse ist nicht so einfach. Es gibt verschiedene Methoden dies zu finden. Eine wäre das Probieren und eine weitere der erweiterte euklidische Algorithmus. In vielen kryptographischen Verfahren muss ein multiplikatives Inverses ermittelt werden. Aber zurück zum Thema. Hier werde ich es durch probieren ermitteln. Bei größeren Modulos wäre dies aber nicht praktikabel.

k₁^.k₁^-1=1

5^.k₁^-1=1

5^.6=4 mod 26

5^.7=9 mod 26
.
.
.
5^.21=1 mod 26

Folglich ist 5^-1=21 mod 26.

Auf zum Entschlüsseln:

x₁=(y₁+k₂^-1)^.k₁^-1=(12-3)^.21=7 mod 26.

Bei Anwendung wie End-Zu-End-Verschlüsselung wird natürlich nicht die Caesar-Verschlüsselung benutzt. Aber sie ist ein schönes Beispiel, um mit dem Thema etwas warm zu werden. Auch im alten Rom soll diese Form der Verschlüsselung auch schon bekannt gewesen sein, daher rührt auch der Name.

Im 2. Weltkrieg gab es auch eine spannende Form der symmetrischen Verschlüsselung - namentlich Enigma. Diese hat multiple additive Schlüssel benutzt und auch hier mussten Sender und Empfänger über den selben Schlüssel verfügen. Eingesetzt wurde dieses Verfahren hauptsächlich auf deutschen U-Booten. An der Entschlüsselung haben sie mit Erfolg sich Engländer abgerackert.

Sie benutzten zum Beispiel Häufigkeitsverteilungen. So ist in der deutschen Sprache e der häufigste Buchstabe. Ohne Computer war es allerdings extrem aufwendig. Historisch ist es aber ein entscheidender Punkt, wo Mathematik ein neues Anwendungsgebiet bekommen hat.

Zahlentheorie galt bis dato als so reine Mathematik, dass man glaubte sie fände keine Anwendung in der echten Welt. Heute basieren allerdings alle kryptographischen Verfahren auf ihr.

Im nächsten Teil werden wir uns daher in die geniale Welt der asymmetrischen Verfahren wagen.

Quellen

1. Albrecht Beutelspacher, Lineare Algebra
2. https://de.wikipedia.org/wiki/Caesar-Verschl%C3%BCsselung
3. 
4. https://de.wikipedia.org/wiki/Symmetrisches_Kryptosystem

---

Cryptographic methods -Let's do the math - part 1 (ENG)

^source

We all move in the cryptocosm and be it at least on Hive. As the term cryptocurrency already suggests, cryptocurrencies have to do with cryptographic procedures. But what kind of cryptographic processes are there and what do they have to do with blockchain?

One thing in advance, I've done some research on the topic and I'm going to look at it more from a mathematical perspective and less from a computer science perspective.

I will distinguish between three principles and also go into more detail on some procedures.

1. Symmetric Methods
2. Asymmetric Methods
3. One-Way Functions

Asymmetric procedures are those procedures that are used among others in the blockchain world. One-way functions are also relevant for crypto geeks, as the so-called hashing is a cryptographic one-way function. Another point is digital signatures. They also make use of asymmetric methods and since transactions are digitally signed on a blockchain, for example on Hive, we will take a closer look at that.

Of course, we also need some math for all the procedures. So I'll go into symmetric procedures first so we can get a feeling for the math we'll need.

Symmetric methods

Even today, symmetric encryption methods still find their use because they are faster than asymmetric encryption methods, for example WhatsApp's end-to-end encryption. (More accurate, however, is a combination of symmetric and asymmetric encryption).

Before we can really get started, though, we need some math. We don't want to go very deep into this one, though - so don't worry.

Groups

First, let's clarify what a group is. We have a set and an arithmetic operation. The set must be complete, i.e., each arithmetic result must be within the group again.

If we have for example the set {1,2,3,4} and the arithmetic operation + this set would not be complete. For example 3+4=7 and 7 is not in our set. The set of natural numbers {1,2,3,4,5...} would be complete concerning the addition.

A set G including an arithmetic operation o is called a group, if the following three axioms hold:

1. Existence of a neutral element e
   aoe=a

2. Existence of an inverse element a^-1
   aoa^-1=e

3. Associative Law
   (aob)oc=ao(boc)

Now let's feed this with an example. Are the integers {0,1,-1,2,-2,3,-3...} a group with the arithmetic operation +?

This question should not be very difficult to answer. We can simply check the three axioms.

1. Is there a+e=a? The neutral element will probably be 0. Because a+0=a. I.e. 0 is the neutral element of the addition. If you ever wondered why mathematicians are always looking for the "zero" (zero vector, zero matrix etc.), here is the answer.

2. Of course to a there is also a^-1. Because a+a^-1=a+(-a)=a-a=0. By the way, the inverse is important so that we can transform equations.

3. This law is also valid. I pinch myself a reasoning at this point. The first two axioms are the relevant ones for us.

So we see that the integers are a group with the arithmetic operation +. Are they also a group with the arithmetic operation ^.?

1. The neutral element would be 1, since a^.1=a. Similar to 0, mathematicians are also constantly looking for "1" (unit matrix, identity, etc.).

2. Unfortunately, we do not find an inverse in the integers. Thus, 5^.5^-1=5^.(1/5)=1. However, 1/5 would not be an integer. Thus, the integers would not be a group. It should also be noted at this point that in the following we do not include "0" in multiplication, since "0" has no multiplicative inverse.

In cryptography, however, we will not do classical addition or classical multiplication. We will be doing modulo arithmetic. I've explained here before how to compute modulo.

But I will repeat it again briefly. Modulo is sharing with remainder but you only compute with the remainder. For example, we could check if the F₅={0,1,2,3,4} is a group for the arithmetic operation ^.. Imagine the F₅ as a set in which one may only calculate modulo 5.

So 3+4=7=2 mod 5 and 3^.4=12=2 mod 5.

We could also ask ourselves what is 4²⁰²¹ mod 5, for example.

Easy:

4²⁰²¹=(-1)²⁰²¹=-1=4 mod 5.

But back to the question if it is a group:

1. The neutral element is simply 1, how could it be otherwise.

2. For the question about the inverse it becomes already more difficult. Does every element of our set have an inverse? 1^.1=1 mod 5, 2^.3=6=1 mod 5, 3^.2=6=1 mod 5 and 4^.4=16=1 mod 5. As already mentioned, we exclude 0 from multiplication, because 0 has no inverse.

3. The associative law is also valid but we will not check that.

Consequently, all axioms hold and it is a group.

Let's return to symmetric encryption.

Caesar encryption

In symmetric encryption, the sender and receiver both have the same key, which is also the main problem with such methods. This is because a key exchange must take place for this purpose. Here an attacker could of course become active and try to get the key.

The best known idea is simply to shift the alphabet by k digits and thus encrypt the text. This is called additive Caesar encryption. For this we assign a number to each letter (A=0,B=1,C=2...).

The word H I V E would be 7 8 21 4. If our key is k=5 we have to calculate +5 mod 26.

H I V E

7 8 21 4

12 13 0 9

M N A J

But this encryption would be very easy to crack, because we have only 26 possibilities to choose a key.

To spice things up we could also use a multiplicative Caesar encryption.

Let's take k=5 again as the key. 7^.5=35=9 mod 26, 8^.5=40=14 mod 26, 21^.5=105=1 mod 26 and 4^.5=20 mod 26.

*H I V E

7 8 21 4

9 14 1 20

J O B U

Of course there are also only 26 possibilities to take a key. And for multiplication we should not necessarily take numbers like 13 or 2. But we could increase the key space significantly if we do both variants at the same time.

For this, let k₁=5 and k₂=3. We want to encrypt with y=x^.k₁+k₂. And again we want to encrypt the word HIVE. Let's see:

y₁=7^.5+3=12 mod 26

y₂=8^.5+3=17 mod 26

y₃=21^.5+3=4 mod 26

y₄=4^.5+3=23 mod 26

*H I V E

7 8 21 4

12 17 4 23

M Q E X

But how is the whole thing decoded now? I have already mentioned that the inverse is needed to convert equations. I.e. we would have to convert y=x^.k₁+k₂ to x:

y=x^.k₁+k₂ |+k₂^-1

y+k₂^-1=x^.k₁+k₂+k₂^-1

y+k₂^-1=x^.k₁+0

y+k₂^-1=x^.k₁ |^.k₁^-1

(y+k₂^-1)^.k₁^-1=x^.k₁^.k₁^-1

(y+k₂^-1)^.k₁^-1=x^.1

x=(y+k₂^-1)^.k₁^-1

Now we will still perform the decoding on the example y₁.

x₁=(y₁+k₂^-1)^.k₁^-1

x₁=(7+k₂^-1)^.k₁^-1

So we need k₂^-1, which is the additive inverse to k₂=3, and k₁^-1, which is the multiplicative inverse to k₁=5.

Let's start with the additive inverse. It holds:

k₂+k₂^-1=0.

In the integers, k₂+k₂^-1=3+3^-1=3-3=0. We can also apply this to modulo 26. Because -3=23 mod 26. Consequently holds:

k₂+k₂^-1=3+k₂^-1=3-3=3+23=0 mod 26.

The multiplicative inverse is not so simple. There are several methods to find this. One would be trial and error and another would be the Extended Euclidean Algorithm. In many cryptographic methods, a multiplicative inverse must be determined. But back to the topic. Here I will determine it by trial and error. But this would not be practical for larger modulos.

k₁^.k₁^-1=1

5^.k₁^-1=1

5^.6=4 mod 26

5^.7=9 mod 26
.
.
.
5^.21=1 mod 26

Consequently, 5^-1=21 mod 26.

On to decode:

x₁=(y₁+k₂^-1)^.k₁^-1=(12-3)^.21=7 mod 26.

Of course, in application like end-to-end encryption, Caesar Encryption is not used. But it is a nice example to warm up a bit with the topic. Also in ancient Rome this form of encryption was already known, that's where the name comes from.

In WW2 there was also an exciting form of symmetric encryption - called Enigma. This used multiple additive keys and also here sender and receiver had to have the same key. This method was mainly used on German submarines. The English have successfully worked on the decryption.

They used for example frequency distributions. Thus in the German language e is the most frequent letter. Without computers, however, it was extremely laborious. Historically, however, it is a crucial point where mathematics got a new field of application.

Until then, number theory was considered so pure mathematics that it was believed to have no application in the real world. Today, however, all cryptographic methods are based on it.

In the next part, we will therefore venture into the ingenious world of asymmetric methods.

Sources

1. Albrecht Beutelspacher, Lineare Algebra
2. https://de.wikipedia.org/wiki/Caesar-Verschl%C3%BCsselung
3. 
4. https://de.wikipedia.org/wiki/Symmetrisches_Kryptosystem