<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Sebastia Agramunt-Puig on Medium]]></title>
        <description><![CDATA[Stories by Sebastia Agramunt-Puig on Medium]]></description>
        <link>https://medium.com/@sebastiaagramunt?source=rss-172fdcae7d76------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Stories by Sebastia Agramunt-Puig on Medium</title>
            <link>https://medium.com/@sebastiaagramunt?source=rss-172fdcae7d76------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 14:36:38 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sebastiaagramunt/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Discrete logarithm problem and Diffie-Hellman key exchange]]></title>
            <link>https://sebastiaagramunt.medium.com/discrete-logarithm-problem-and-diffie-hellman-key-exchange-821a45202d26?source=rss-172fdcae7d76------2</link>
            <guid isPermaLink="false">https://medium.com/p/821a45202d26</guid>
            <dc:creator><![CDATA[Sebastia Agramunt-Puig]]></dc:creator>
            <pubDate>Mon, 23 Nov 2020 08:51:53 GMT</pubDate>
            <atom:updated>2020-11-23T08:51:53.944Z</atom:updated>
            <content:encoded><![CDATA[<p><em>In the previous post we learned what are ciphers and how can two parties establish a secure communication when they both hold the same secret key, for instance using a stream cipher. In this post we will see how they can agree on a common key through an insecure channel. You can find all my code for this post </em><a href="https://github.com/SebastiaAgramunt/Cryptography"><em>here</em></a><em>.</em></p><p>I hope that in the previous post I convinced you that stream ciphers are good practical ciphers (used in real cryptographic applications like <a href="https://en.wikipedia.org/wiki/A5/1">mobile phone communications</a>). For the stream cipher to be secure we require that Alice and Bob agree on a <a href="https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator">cryptographically secure pseudo-random generator</a> algorithm (CPRG) and a private key that act as a seed for the CPRG. Stream ciphers are just one class of ciphers from a broader family called <strong>symmetric ciphers </strong>(check chapters 3 to 6 from the <a href="https://www.cs.umd.edu/~jkatz/imc.html">book</a> of Katz and Lindell where they explain <strong>private key cryptography</strong> or <strong>symmetric cryptography</strong>) whose common characteristic is that the two communicating parties Alice and Bob hold the same private key that is used for both encryption and decryption of the message.</p><p>Ok, so now we have a plethora of symmetric ciphers that one can use to communicate securely with another party. The only missing ingredient is how can Alice and Bob agree on a specific secret key (a string of bits or equivalently an integer) when communicating through a completely insecure channel. Let me reformulate this in a more mundane example. Imagine that Alice and Bob want to establish a common secret key, and they are located on opposite sides of a room full of people (the eavesdroppers). They can just communicate shouting out loud integer numbers through the room so Charlie (some random person that is in the middle of the room) can hear everything they say. Surprisingly Alice and Bob can agree on a common secret key even if Charlie is listening to all of their messages. If you you want to know how? Just keep on reading.</p><h3>The discrete logarithm problem</h3><p>Warning!. For this section, you may need to refresh an older <a href="https://medium.com/@SebastiaAgramunt/number-theory-for-cryptography-and-privacy-preserving-machine-learning-866b1f171c51">post</a> on algebra and modulo arithmetics from this series.</p><p>You may know logarithms from your math class at school. They are pretty simple. The function logarithm is normally represented as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/102/1*sOoY-wgOgWvPuiHMeWRi_A.png" /></figure><p>where <strong>x</strong>, <strong>y</strong> and <strong>b</strong> are related by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/58/1*SWo5hUXNjZ1cn5Q3SHG0lQ.png" /></figure><p>here <strong>b</strong> is known as the base of the logarithm. The logarithm problem is the problem of finding <strong>y</strong> knowing <strong>b</strong> and <strong>x</strong>, i.e. calculate the logarithm of<strong> x </strong>base<strong> b</strong>. This is super straight forward to do if we work in the algebraic field of real numbers, just have a look at the logarithm graph for base 10:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xXgMsJFPClLMFdfKwxH86Q.png" /><figcaption>logarithm base 10 as a function of x.</figcaption></figure><p>Nice graph, smooth, derivable… Now if I give you the following values of <strong>y</strong>=[10, 100, 1000] could you compute <strong>x</strong> knowing that <strong>b</strong> is 10? Pretty easy, those are [1, 2, 3]. If we pick values in the middle like for instance 1.5 we just need to apply simple <a href="http://numerical.recipes/">numerical methods</a> knowing that the function is smooth and derivable but at first glance you can guess the value is between 1 and 2.</p><p>The logarithm problem can be reformulated when instead of working in the real numbers field we work on the prime modulo algebraic field (now that you know what is a <a href="https://medium.com/@SebastiaAgramunt/number-theory-for-cryptography-and-privacy-preserving-machine-learning-866b1f171c51">prime modulo field</a> and how to <a href="https://medium.com/@SebastiaAgramunt/prime-numbers-7eab54534809">generate large prime numbers</a>). Specifically, we will only use the algebraic group part of the second operation, the multiplication. This is, the elements {1, 2, 3, … <strong>p</strong>-1} where <strong>p</strong> is a prime number with the operation multiplication modulo <strong>p</strong>.</p><p>The discrete logarithm problem (DLP) reads: Find <strong>y</strong> knowing <strong>x</strong>, <strong>g</strong> and <strong>p</strong> such that:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/133/1*LWaSJUDNSjX0mEcQhD0nTQ.png" /></figure><p>where <strong>p</strong> is a prime number and <strong>g</strong> is what we know as a generator of the group defined by <strong>p</strong>. The generator is simply an element of the field such that by powering it from 1 all the way to <strong>p</strong>-1 it generates all the elements of the group, thus {<strong>g</strong>, <strong>g</strong>², <strong>g</strong>³,…, <strong>g</strong>^(<strong>p</strong>-1)}(mod <strong>p</strong>) are all the elements of the group. Not all the elements of the group are generators and we won’t discuss here how to find them (you can find the algorithm in <a href="https://shoup.net/ntb/ntb-v2.pdf">A Computational Introduction to Number Theory and Algebra</a> by Victor Shoup and my implementation in Python can be found <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/crypt.py">here</a>). We’ll get to the point on why we use a generator for exponentiation later on.</p><p>Let’s take an example with (<strong>g</strong>, <strong>p</strong>) = (27893, 61981) and plot only in the for the ranges of y in between 2000 and 3000 for better visualisation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xRANdl-umegBVgaihEAajw.png" /><figcaption>Plot of x for several values of y for the group defined by <strong>p</strong>=61981 using the group generator element <strong>g</strong>=27893.</figcaption></figure><p>First, a takehome exercice!. I don’t want you to blindly believe that <strong>g</strong>=27893 is a generator, just try it yourself!. Calculate all the powers of 27893 modulo 61981 and check that you generate all the numbers between 1 and <strong>p</strong>-1. Write a simple program on that to verify.</p><p>Now, let’s get back to the problem. If I give you <strong>x</strong>=53434<strong>, g</strong>=27893 and<strong> p</strong>=61981, could you guess from the graph above what’s the value of <strong>y</strong>? (spoiler, its <strong>y</strong>=29 but I bet you can’t tell). This is difficult to see as there’s no apparent pattern here compared to the field of real numbers seen previously. There’s no way also to calculate numerically the solution as before. This is a really hard problem to solve if <strong>p</strong> is a large prime (more on that in the following section).</p><p>Now, why we use a generator <strong>g</strong> instead of any number between 1 and <strong>p</strong>-1? It’s because with <strong>g</strong> we increment the search space, i.e. a priori any number between 1 and <strong>p</strong>-1 is a valid candidate for <strong>y</strong>, the number we are looking for. This makes the problem harder.</p><h3>How hard it is to break the discrete logarithm problem?</h3><p>I hope I have convinced you that finding <strong>y </strong>in the DLP is a difficult task. But how hard is it?. Let’s try to break the DLP problem by randomly guessing the values of <strong>y</strong>.<strong> </strong>This is, given the triplet (<strong>x</strong>, <strong>g</strong>, <strong>p</strong>) we will randomly try different <strong>y </strong>until we find that <strong>x</strong>=<strong>g</strong>^<strong>y</strong>(mod <strong>p</strong>).</p><p>In <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/03_Diffie%E2%80%93Hellman_%26_DiscreteLogProblem.ipynb">this</a> notebook first we generate a random prime number <strong>p</strong> of <strong>n</strong> bits and a corresponding generator <strong>g</strong>. Then randomly pick a value <strong>x </strong>in between 0 and <strong>p</strong>-1 (the secret key). At this point the protocol is set up, now the attack is to try to guess <strong>y </strong>by randomly sampling values in between 0 and <strong>p</strong>-1 and compute <strong>g</strong>^<strong>y</strong>(mod <strong>p</strong>). If this value is equal to <strong>x</strong>, then we would have cracked the DLP. On my computer (a regular laptop) I came up with the following values:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_vCTA3CcMPfRUG0cpm20vQ.png" /></figure><p>In the above table the first column is the number of bits of the random prime number generated, the second the minimum (best case scenario) search space ad the third column the computation time it took to crack the DLP in just one round (for more accurate numbers we ideally should run each case several times and make the average). Recall how fast the difficulty increases, for instance when increasing from 20 to 21 bits we go from 7 seconds to 15 seconds, and that’s a huge increase!. Try it yourself for 32 bits <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/03_Diffie%E2%80%93Hellman_%26_DiscreteLogProblem.ipynb">here</a>, see how long can you wait before aborting the calculation.</p><p>When working with computationally hard problems to solve one can use <strong>The concrete approach definition for computational security</strong> (see <a href="https://www.crcpress.com/Introduction-to-Modern-Cryptography/Katz-Lindell/p/book/9781466570269">An introduction to modern cryptography</a>): A scheme is (<strong>t</strong>, <strong>e</strong>) secure if any adversary running at most during time <strong>t</strong> succeeds to break the code within probability at most <strong>e</strong>.<strong> </strong>Say a supercomputer can do <strong>c</strong> key test per unit time, then at time <strong>t</strong> he will have run <strong>c*t</strong> checks. The probability of guessing the key of length <strong>n</strong> bits is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/129/1*smOVWd_cto-w2ENHfcMjhA.png" /></figure><p>This probability has to be smaller than <strong>e </strong>so that the scheme is (<strong>t, e</strong>) secure<strong>. </strong>Recall that<strong> </strong>as the size of the key (<strong>n</strong>) grows the probability decreases exponentially so comparing we need a lot of time (because it grows linearly) to get to the same probability.</p><p>Just to mention, there’s another approach to computational security that instead of dealing with times it deals with complexity of algorithms. That’s the <strong>asymptotic approach</strong> and you can learn more formally about it in this <a href="https://www.cs.umd.edu/~jkatz/imc.html">book</a>.</p><h3>The Diffie-Hellman key exchange</h3><p>Now let’s get back to the main aim of this post, that is, to find a way for Alice and Bob to agree on a number when communicating through an insecure channel. For this we can exploit the difficulty to crack the DLP problem (see the <a href="https://www.springer.com/gp/book/9781441926746">book</a> of Hoffstein, Pipher and Silverman). In the book you find a nice chart explaining the Diffie-Hellman key exchange:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zjn4vpBqxtkUmwWVc53TNg.png" /><figcaption>Diffie-Hellman key exchange. Table 2.2 from the book of Hoffstein Pipher and Silverman. A masterpiece, you must buy it!</figcaption></figure><p>First Alice and Bob agree on a prime number <strong>p</strong> and a generator <strong>g</strong> of the group of integers mod <strong>p</strong>. This is something public and any eavesdropper knows it. Then Alice and Bob secretly choose two random numbers <strong>a</strong> and <strong>b</strong> respectively in the range between 1 to <strong>p</strong>-1. Now each of them secretly computes <strong>A</strong>=<strong>g</strong>^<strong>a</strong>(mod <strong>p</strong>) and <strong>B</strong>=<strong>g</strong>^<strong>b</strong>(mod <strong>p</strong>). Then Alice sends <strong>A</strong> to Bob and Bob sends <strong>B</strong> to Alice. The malicious eavesdropper can see <strong>A</strong> and <strong>B</strong> but due to the DLP problem has a super hard time when trying to guess either <strong>a</strong> or <strong>b</strong> values (for a sufficiently large <strong>p</strong>). Then Alice secretly computes <strong>B</strong>^<strong>a</strong> (mod <strong>p</strong>)=<strong>g</strong>^(<strong>a</strong>*<strong>b</strong>)(mod <strong>p</strong>)=<strong>sk</strong>. Also Bob secretly computes <strong>A</strong>^<strong>b</strong> (mod <strong>p</strong>)=<strong>g</strong>^(<strong>b</strong>*<strong>a</strong>)(mod <strong>p</strong>)=<strong>sk</strong>. Notice that Alice and Bob compute the same <strong>sk</strong>!.</p><p>We now have a way for two parties to agree on a common key <strong>sk </strong>communicating through an insecure channel. Now they just have to choose the right secure symmetric cipher and start communicating securely!. There are however some attacks that called “man in the middle” that can compromise the establishment of the private key. But don’t worry, we can still establish a common secure key using Diffie-Hellman. For further details on man in the middle attacks and Diffie-Hellman check out the <a href="https://www.youtube.com/watch?v=vsXMMT2CqqE&amp;ab_channel=Computerphile">excellent explanation</a> of Dr. Mike Pound.</p><h3>Takeaways</h3><p>We have seen how difficult it is to compute discrete logarithms over modulo prime groups and how this can help us generate a common secret key in between two parties communicating through an insecure channel. That is the only ingredient we were missing for secure communication once we have a secure symmetric cipher.</p><p>In this post we also assessed what it means for modern cryptography to be secure, that is, a mathematical problem difficult to crack. We’ve seen the concrete and asymptotic approaches of computational security.</p><p>In the next post we will begin exploring the field of secure multiparty computation a subfield of cryptography.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=821a45202d26" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An introduction to secure communication]]></title>
            <link>https://sebastiaagramunt.medium.com/an-introduction-to-secure-communication-f269d6b93d9e?source=rss-172fdcae7d76------2</link>
            <guid isPermaLink="false">https://medium.com/p/f269d6b93d9e</guid>
            <category><![CDATA[privacy-preserving]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Sebastia Agramunt-Puig]]></dc:creator>
            <pubDate>Wed, 14 Oct 2020 22:00:49 GMT</pubDate>
            <atom:updated>2020-10-14T22:10:21.423Z</atom:updated>
            <content:encoded><![CDATA[<p><em>In this post we will see the most basic example for encrypting your messages, then we will show that this by no means is secure and finally we will introduce what it means to have a perfect secrecy scheme and why is not practical. Then, we’ll get to see what are stream ciphers for symmetric encryption. Python code for this post can be found </em><a href="https://github.com/SebastiaAgramunt/Cryptography/tree/master/notebooks"><em>here</em></a><em>.</em></p><p>One of the main objectives of cryptography is to enable secure communication between a sender and a receiver. This means that if someone is intercepting (eavesdropping) the ciphertexts (encrypted messages) sent between parties A and B he is not able to get any information. To introduce nomenclature I will show the most basic cipher, the shift cipher.</p><h3>Shift cipher</h3><p>In the shift cipher (a.k.a Caesar’s cipher), two parties A and B agree on a common key, a number in between 0 to 24, this key is secret and they don’t share it with anybody else. In the shift cipher the key is translated into the number of jumps on the alphabet, let’s take a key (shift) of 3 as an example. The substitution of letters would be:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/610/1*i6Wp471_LRDh_kzyaTs0Uw.png" /><figcaption>Caesar’s cipher substitution for key k=3</figcaption></figure><p>Now imagine that A wants to send to B the message “<em>let the people vote</em>” (a.k.a the message in plaintext), but obviously A cannot send this message as is through an insecure communication channel so he has to transform the message to the encrypted space as “<em>ohw wkh shrsoh yrwh</em>” (this is known as the ciphertext), that is, it substitutes “l” by “o”, “e” by “h” and so on as depicted in the substitution image above for key=3. Then he can send the ciphertext through the insecure channel and people eavesdropping this are not able to decrypt (reveal) the original message unless they have the secret key.</p><p>This cipher is very simple, to crack it the eavesdropper just needs to try all the possible secret keys (shifts) from 0 to 24. For instance if an eavesdropper C tried to decrypt the message using the key=1 he would have the decrypted message “<em>ngv vjg rgqrng xqvg” </em>when observing the previous ciphertext (you can try it easily in this <a href="https://cryptii.com/pipes/caesar-cipher">webpage</a>)<em>, </em>obviously this message does not make any sense in english so he’d think that this is not the correct key and would try a new one. It is easy to see that it won’t take him very long to find that the original key for encryption was 3 and therefore decrypt all the messages that he was able to grasp between A and B.</p><h3>Better security by increasing the key space</h3><p>We’ve seen that if the key space (number of possible secret keys) is small it is not difficult to find the correct key and then decrypt all the messages. So, we can increase this key size and then the probability for the attacker to find the correct key is reduced (or, he’ll have to invest a lot of time to find it).</p><p>In the practical example I will show in this section (have a look at the code in the <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/06_Classical_cipher_mono_alphabetic.ipynb">notebook</a>) we are going to work with an improved cipher, called the mono-alphabetic substitution cipher. In this cipher we substitute the letters “a, b, c,..., z” with a random permutation of those. For instance a key can be the one depicted on the image below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/778/1*X82l94s08uom5-41rcKmuA.png" /></figure><p>in this case the letters “a”, “b”, “c” … from the message are mapped to the corresponding values below “a”, “v”, “s”… It is a simple substitution. The key space of this cipher is much larger compared to the Shift cipher, we can in fact generate 24!=24*23*22…*2*1=620448401733239439360000 possible keys. Looks pretty secure, right?. Brute force trial and error of the keys would take long (the probability of guessing the correct key in 1 trial is (1/24!=1.61E-24) and it doesn’t seem practical.</p><h3>Leaking information from ciphertexts</h3><p>In the mono-alphabetic cipher it may be difficult for the attacker to get the exact key but still he can get some valuable information by just looking at the ciphertexts. Imagine that the attacker knows the language of communication in between the two parties (Alice and Bob) and so by just observing the ciphertexts he can infer information from the messages. Imagine this language is plain english, the attacker then knows that some words are more frequent than others, for instance “the”, “be”, “to”, “of” or “and” are listed as the <a href="https://en.wikipedia.org/wiki/Most_common_words_in_English">most frequent words in english</a>. This means that the attacker will observe many times the words “dco”, “vo”, “dk”, “ki” and “agb” in the ciphertexts (if we use the substitution cipher introduced in the example). Now he can exploit that to find some letter substitutions in the key.</p><p>In the example of the <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/06_Classical_cipher_mono_alphabetic.ipynb">notebook</a> I used a much simpler but similar attack. In this, I used text of the famous George Orwell’s book 1984. First I calculated the frequencies of letters (not words as before) taking all the words in the book and got ‘a’ appearing 36548, ‘b’ 7668 times, ‘c’: 11642 times, ‘d’: 19033… in sorted order. This is my source of truth for frequency of letters in the english language. Then, in order to estimate a regular message in plain english I sampled a chunk of 5% length of the book. With this chunk we calculate the ciphertext (the simple substitution above) and compute the frequencies of the words on it. Now, just by comparing the frequencies in the ciphertext and those of the english language we have been able to estimate 8 correct substitutions of the letters out of 24. How? Just by having a closer look at the ciphertexts with the prior that we know the language of communication is english. The conclusion: One can infer information from the original message just by looking at the ciphertext. This is an unwanted result.</p><h3>Perfect secrecy and the one time pad</h3><p>Can we find a way such that the ciphertext does not contain any information?. First let me write a definition (a more formal definition can be found in the <a href="https://www.cs.umd.edu/~jkatz/imc.html">book</a> of Katz and Lindell) . An encryption scheme is considered to be perfectly secret if</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/167/1*P-Qv9i_XfHv6s0FR5oJE2Q.png" /><figcaption>An encryption scheme is perfectly secret if the probability of a message does not change by the observation of a ciphertext.</figcaption></figure><p>where <strong>m</strong> represents all possible messages and <strong>c</strong> all possible ciphertexts. This means that the probability of finding a specific message does not change by the observation of any cipertext, i.e. the ciphertext does not contain any information about the message.</p><p>There’s a way to achieve perfect secrecy, and this is through <a href="https://en.wikipedia.org/wiki/One-time_pad">one time pad</a>. Let me explain it with a simple example. Imagine the scenario where Bob is a submarine captain of a secret army and Alice is his contact on the mainland. In the next mission Bob is told to go to the enemy base and wait for a communication from Alice of “attack” or “retreat” at exactly 4 p.m. They therefore want to communicate with messages of 1 bit, (1 means attack and 0 means retreat). The enemy has been informed by one of his spies that Bob is going to his base at 4 p.m and will be waiting for orders from Alice. He is also aware of the code they use. If the enemy knows that Bob is not attacking he will let him go (let’s assume the enemy is much weaker than Bob), otherwise he will try to attack first with all his force.</p><p>The first thing that Alice and Bob do is to meet in person at the base and agree on a common key for communication, this key has to be the same length as the message they want to send (in our case one bit). Then they agree that they calculate the ciphertext by <a href="https://en.wikipedia.org/wiki/Exclusive_or">XOR</a>ing the message with the key and do again XOR for decrypting the message (recall that XOR is the same as to apply addition modulo 2 operation). In the following table it is represented the encryption of one bit using XOR</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/508/1*-xKg45jSZ0xBP-2HdxN-lw.png" /><figcaption>XOR operation for the one time pad for messages of 1 bit.</figcaption></figure><p>Once they agreed on a key (and are 100% sure nobody else knows it) they can communicate once through an insecure channel. Le’t say the key is 1. If Alice wants Bob to attack, she will send the ciphertext 0, otherwise 1. Now the attacker can observe this ciphertext but has no information whatsoever on the key, let’s say he observes ciphertext=1, from the above he can say that if the secret key is 0 then the order is attack but if it is 1 the order is retreat so P(attack)=P(retreat)=0.5. So he gets exactly the same probability for either attack or retreat, that means the ciphertext does not contain any information and he hasn’t learned anything new from the intentions of the secret army. Further explanation and implementation in Python can be found <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/10_One_Time_Pad_Encryption.ipynb">here</a>.</p><p>The one time pad can be extended to many bits, for instance if the message is of 256 bits, the binary key has to be of 256 bits too because we are masking 1 bit by 1 bit (this is a requirement from Shannon’s theorem for perfect secrecy found on <a href="https://www.cs.umd.edu/~jkatz/imc.html">this</a> book). It is important to notice however that the key can only be used to transmit one message. If more messages were transmitted with the same key one could start computing the frequencies of the bits and eventually make statistics similar to what we did in the previous section.</p><p>One time pads are not practical for implementation because of the following reasons:</p><ul><li>The key has to be at least as long as the message one wants to transmit. This means we have to store a lot of information. For instance if we transmit a text message in ASCII encoding (8 bits per letter) and send a word of 10 letters we would need a key of 80 bits at least.</li><li>For perfect secrecy one has to use a new key every time. When Alice and Bob meet in person they will have to exchange a lot of keys and use one by one sequentially for their communications. This again is a lot of information and is impractical.</li><li>Alice and Bob have to make sure that they are the only ones that know the key. In the examples I always stated that they have to meet in person, this is a way to make sure that nobody is spying them. When using computers one wants to establish a secure communication through an insecure channel like the internet between two computers that are physically very far away. This makes the one time pad totally impractical.</li></ul><h3>Improving the one time pad: stream ciphers</h3><p>The general idea of the one time pad is used in <a href="https://en.wikipedia.org/wiki/Stream_cipher">stream ciphers</a>. Here we need the notion of a pseudorandom generator (see <a href="https://www.cs.umd.edu/~jkatz/imc.html">Introduction to modern cryptography</a> from Katz and Lindell), this is an algorithm that inputs a number (a.k.a the seed) and outputs what looks like a random string of bits. In essence a good pseudorandom generator (PRG) must output bit strings that are difficult to distinguish from pure random.</p><p>The PRG algorithm and the seed (the secret key) are shared among Alice and Bob so they can generate the same <em>stream</em> of “close-to-random” bits. These stream is used to pad the message and encrypt/decrypt the same way we did (XORing) in the one time pad in the previous section. Yes!, this is very similar to the one time pad!. But not exactly the same…</p><p>As expected there’s no free lunch. PRGs do not produce pure randomness. Pure randomness would mean that if one observes the output of <strong>n</strong> bits produced by the PRG (without knowing the seed) the probability of observing either 1 or 0 on the next bit generated by the PRG is exactly 0.5. This can’t be the case because the PRGs are deterministic algorithms. So there’s still information leakage from the ciphertext.</p><p>Alice and Bob can generate exactly the same stream of bits if they know both, the PRG algorithm and the seed to initiate it. To an adversary (knowing the PRG algorithm but not the seed) it is very difficult do guess the sequence computationally speaking so we would say this is secure. We can even measure the security of the stream cipher by comparing different PRGs, i.e. one stream cipher is more secure than another stream cipher if the pseudo-random numbers generated by the first looks more random (informally speaking) to an observer looking at the generated bits of both.</p><p>And finally good news! stream ciphers are used in modern day communications!. For instance <a href="https://en.wikipedia.org/wiki/A5/1">A5</a> is used in cell phone communications but as we said it is not perfectly secure since the PRG generates pseudo-random deterministic bits that are not entirely random.</p><p>I won’t extend on stream ciphers here but I hope you got the general idea. For further details have a look at the <a href="https://www.youtube.com/watch?v=AELVJL0axRs&amp;ab_channel=IntroductiontoCryptographybyChristofPaar">lecture</a> of Prof. Christof Paar on the topic. He approaches the topic differently, first explaining stream ciphers and later on perfect secrecy. Another excellent reference is the <a href="https://www.cs.umd.edu/~jkatz/imc.html">book</a> of Katz and Lindell.</p><h3>Improving the stream cipher using quantum physics</h3><p>Now imagine that Alice and Bob could generate the same pure random streams of bits for a moment. For an attacker eavesdropping all the communications between Alice and Bob the ciphertexts would look totally random, that’s the case of perfect secrecy!. Don’t overreact but we are close to find the perfect cipher!. Now the question. Can we generate <strong>pure correlated randomness</strong> between Alice and Bob?</p><p>Let’s think how we can generate pure randomness first. Just use a physical process like thermal fluctuation on a CPU of your computer. Say for instance that normally the CPU is at X temperature, then if at the moment of generating one random bit we measure the temperature and is below X we output 0 otherwise 1. A better way to generate random noise is to prepare a quantum state for an electron in which the probability when measuring its spin is exactly 0.5 for up or down.</p><p>Ok, we got ways using physics to generate pure randomness on Alice and Bob’s ends. However you have to remember that Alice and Bob have to generate exactly the same stream of bits i.e. the same randomness. We cannot achieve this using classical thermal fluctuation so Alice and Bob need to have some sort of correlation between them. Using the properties of <a href="https://en.wikipedia.org/wiki/Quantum_entanglement">quantum entanglement</a> (see <a href="https://en.wikipedia.org/wiki/Quantum_key_distribution">quantum key distribution</a>) Alice and Bob and can prepare two physical quantum states on their end that are “correlated” so they can both generate the same pure randomness (again this comes from the random nature of quantum physics).</p><p>Yes… this is far beyond what I wanted to explain in this post, but I come from a physics background and it was very tempting to at least mention.</p><h3>Takeaways from this post</h3><p>We presented the shift cipher and the substitution cipher as simple examples to illustrate the problem of the ciphertext carrying information from the message. We’ve seen with a simple attack on those ciphers how can one get information from the messages by just observing the ciphertexts. Then stated the problem of getting ciphertexts not containing any information from the message, i.e. perfect secrecy and we’ve seen that even though we can achieve it with the one time pad this is not a good practical solution for several reasons. A more practical approach is to use stream ciphers where take the same philosophy of padding the message with a random stream of bits. Here however we use pseudo-random generators to generate the noise, and the problem is that this noise is not purely random so stream ciphers are not perfectly secure but practical in many applications such as mobile communications. One way to make stream ciphers perfectly secure is to generate the randomness using quantum physics, an active field of research nowadays.</p><p>Please if you liked, give me some claps on medium or star my <a href="https://github.com/SebastiaAgramunt/Cryptography">repository</a> on Github.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f269d6b93d9e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Prime Numbers]]></title>
            <link>https://sebastiaagramunt.medium.com/prime-numbers-7eab54534809?source=rss-172fdcae7d76------2</link>
            <guid isPermaLink="false">https://medium.com/p/7eab54534809</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[security]]></category>
            <dc:creator><![CDATA[Sebastia Agramunt-Puig]]></dc:creator>
            <pubDate>Thu, 08 Oct 2020 09:52:27 GMT</pubDate>
            <atom:updated>2020-10-10T10:11:41.270Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Prime numbers are the building blocks of arithmetics. In this short post we will investigate some attributes of prime numbers and how to work with them in a computer. All the algorithms here can be found in a python </em><a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/02_Prime_Numbers.ipynb"><em>notebook</em></a><em>.</em></p><p>One of the main applications of prime numbers is in some algorithms related to cryptography (e.g. RSA) and therefore it is related to techniques developed for privacy preserving machine learning. In a previous post we have defined groups and fields using prime numbers and our main aim in this post is to show how to calculate prime numbers and check whether a certain number is prime or not. Due to the mathematical importance of primes I considered worthwhile to write a full post about them.</p><p>A prime number is a natural number that is only divisible by himself and 1. For instance 7 is a prime number because there’s no natural number smaller than 7 that divided by 7 results in an integer. Some sorted prime numbers are {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, …}.</p><h3>The building blocks of arithmetics</h3><p>Prime numbers are considered the building blocks of arithmetics because no matter what natural number you may think of, you can express it as product of prime numbers. For instance, take 30, it can be decomposed as 2·3·5. Or 123456 in 2^6·3·643. The process of decomposing a number to its prime number factors is called it factorisation.</p><p>The <a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic">fundamental theorem of arithmetics</a> (a.k.a unique factorisation theorem) states that every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and furthermore this representation is unique. So given an arbitrary integer <strong>a </strong>we can write it as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/176/1*4xs0GyQ7M9_pN_0paOdIiA.png" /><figcaption>unique factorisation of a composite number</figcaption></figure><p>where the p’s are prime numbers and e’s are the exponentiation of those.</p><p>But let’s get back to topic, we are interested in cryptography, what does all this have to do with it?. Well, in modern cryptography one tries to find hard mathematical problems to solve that are easy to check. Factorisation of prime numbers is a very difficult task to solve. There are algorithms like <a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm">Pollard’s factorisation</a> or <a href="https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization">Lenstra elliptic-curve factorisation</a> that are efficient but if you have a quantum computer at hand the best by far is the <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm">Shor algorithm</a> (it is polynomial in log(N)). In <a href="https://en.wikipedia.org/wiki/RSA_(cryptosystem)">RSA</a> algorithm one chooses two large prime numbers <strong>p</strong> and <strong>q</strong> and compute <strong>N</strong>=<strong>p</strong>·<strong>q</strong>, the task of the adversary to break the code is to find the factors of <strong>N</strong>. For sufficiently large prime numbers the probability of solving this task by chance is negligible and the classic factorisation methods take too long so in practice it is impossible to crack in today’s computing power based on binary operations. Conversely having <strong>p</strong> and <strong>N</strong> it is very easy to check if <strong>p</strong> is a factor of <strong>N </strong>with one operation. This is also a requirement to modern crypto protocols.</p><h3>How many prime numbers are there? Can we find a “magic formula” to get them all?</h3><p>It was proven by Euclid back in 300 BCE that there are infinitely many prime numbers. The largest one found as of August 2020 is 2^82589933-1 and has 24,862,048 digits when written in base 10.</p><p>It would be nice to have a formula that when you input “give me the 532 prime” it would output 3833 (the 532th prime), all that taking O(1) compute time. Unfortunately this formula does not exist and finding new prime numbers take a lot of computational effort. That means that they are not predictable and this is one of the mysteries on primes… once you see a prime you don’t know when you’ll find the next one. Is there some kind of random/chaos in prime number structure? Nobody knows yet.</p><p>Even though we can’t predict primes with a formula we can calculate the probability of finding a prime number in between a range of numbers. We define Pi(x) as the number of prime numbers smaller than x. For instance, Pi(20)=8, because prime numbers smaller than 20 are {2, 3, 5, 7, 11, 13, 17, 19}. Therefore, to calculate the number of primes between x2 and x1 (x2&gt;x1) we just need to subtract both Pi(x2)-Pi(x1). Here Pi(x) is exact calculation and we have to do it numerically. The <a href="https://en.wikipedia.org/wiki/Prime_number_theorem">prime number theorem</a> establishes the asymptotic distribution of prime numbers by approximating the count to x/ln(x)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/203/1*lZ1CWioPI9-wdLmtk2MVEg.png" /></figure><p>A graphical representation of this result is shown below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1IJCuiBHEfhQ_Fyh9oWGng.png" /><figcaption>Ratio of prime number counting function to two approximations. From <a href="https://en.wikipedia.org/wiki/Prime_number_theorem">Wikipedia</a></figcaption></figure><p>In the graph you can see how the count of prime numbers (the exact one) divided by the approximation tends to 1 for large x for the two approximations, the quotient and the integral. Actually the best approximation is the integral one. This result is very interesting and took many years to find, it gives some structure to this madness of prime numbers. But still, we can’t predict them and this is good for crypto!.</p><h3>Primality testing and prime generation</h3><p>In this section we investigate how to find prime numbers and test if an arbitrary number is prime.</p><h4>A naive way to generate primes</h4><p>The natural way to generate prime numbers is to start from the smallest one {2} and test if the next one (3) is divisible by 2, since it is not, we add it to the list, then we have {2, 3}. We go to test 4 now, since it is divisible by one of the primes we already have (2) we don’t add it to the list and we try the next one, 5. 5 is not divisible neither by 2 nor by 3 so we add it to the list, {2, 3, 5} and so on… This is a very computationally intensive algorithm since all the time you have to check your full list that, by the way, is increasing every time you find a new prime.</p><h4>The sieve of Eratosthenes</h4><p>A faster way to generate prime numbers is using the <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">sieve of Eratosthenes</a> where basically you build a list of all the natural numbers from 1 to <strong>n</strong> (<strong>n</strong> is the natural number below which you want all the primes) and remove all the multiples of the newly find prime. Say we want the prime numbers smaller than <strong>n</strong>=120. The algorithm starts with 2, then you discard its multiples (2, 4, 8, …, 120), you go for 3 and you know it is prime because it hasn’t been discarded, so you eliminate multiples of 3 that haven’t been discarded (3, 9, 12, 15…). The next number is 4 and has been discarded so you go to 5 and add it as prime, then eliminate its multiples… You can find a nice implementation in python <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/crypt.py#L51">here</a>.</p><h4>Primality testing and Miller-Rabin algorithm</h4><p>All the approaches so far seem to be very lengthly… in cryptography you often work with 256 bit prime numbers (2²⁵⁵ to 2²⁵⁶). Now, you can’t generate all prime numbers up to 2²⁵⁶ and then choose one at random, for this you need to use a test of primality. Basically what you do is draw a random natural number and then check whether this number is prime or not.</p><p>So given a natural number <strong>n</strong>, how can you tell if <strong>n</strong> is prime or not? Remember first Fermat’s little theorem: Let <strong>p</strong> be a prime number and let <strong>a</strong> be any integer then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/151/1*G3fTvph9GbCjSzV-a6nT6g.png" /></figure><p>We may use it to check if <strong>n</strong> is prime. If we plug <strong>n </strong>instead of<strong> p </strong>to the above equation (taking for instance. <strong>a</strong>=2) and find that a^{n-1}(mod n) is 1 then can we say that <strong>n </strong>is prime?. The answer is no, because Fermat’s little theorem just goes in one direction (we need to know for sure that <strong>p</strong> is prime). It does however give a good indicative that maybe <strong>n</strong> is prime. So what if we test many different <strong>a</strong>? If we find that the power is 1 for all of them can we say that <strong>n</strong> is prime? Unfortunately the answer is again no. There are in fact numbers known as Carmichael numbers that are composite and its powers a^(n-1) are always 1. A well known Carmichael number is 561=3·11·17 and whose powers are</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/169/1*XSXpfkhRNSsaJnzJh_Sx9w.png" /><figcaption>powering the Carmichael number 561</figcaption></figure><p>for all <strong>a</strong> smaller than 561.</p><p>Seems we are in a cul-de-sac situation… But hopefully we have the Miller-Rabin algorithm to help us. This test was developed by Miller in 1976 as full deterministic test but then modified by Rabin in 1980 to make it a probabilistic algorithm. In order to circumvent the Carmichael numbers let me make the following proposition: Let <strong>p</strong> be a prime (different from 2) then we can write <strong>p</strong> in the form of</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/108/1*G3lK8e14DeUwWciPuL1HrQ.png" /></figure><p>where <strong>q</strong> is an odd number and <strong>k </strong>an integer. Now let <strong>a</strong> be any number not divisible by <strong>p</strong>. Then one of the following two conditions is true</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/169/1*qEy2B8H89_7T4NzrLWsZ6w.png" /></figure><p>or</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/175/1*kbmWJq1FijiBjtzn8n7IUg.png" /></figure><p>for <strong>c</strong> in {1, 2, 4, …, 2^k}. You can find the proof of this proposition is the <a href="https://www.springer.com/gp/book/9781441926746">book</a> of Hoffstein, Pipher and Silverman. This happens strictly when <strong>p</strong> is prime but let’s substitute this <strong>p</strong> for an arbitrary number <strong>n</strong>. We can write <strong>n</strong>-1=2^<strong>k</strong>*<strong>q</strong> and find <strong>a</strong> such that both conditions above are <em>not</em> fulfilled, then we call <strong>a</strong> a Miller-Rabin witness for the compositeness of <strong>n</strong>. I.e. if we find such <strong>a</strong> we know for sure that <strong>n</strong> is composite.</p><p>Ok, but how many random <strong>a</strong>’s should one test to give a certainty of say 99% that the number <strong>p</strong> is probably prime?. There’s another proposition that assesses that. Let <strong>n</strong> be an odd composite number, then at least 75% of the numbers between 1 and <strong>n</strong>-1 are Miller-Rabin witnesses for <strong>n</strong>. This means that if we randomly sample 10 distinct values of <strong>a</strong> in the range of 1 to <strong>n</strong>-1, the probability of hitting at least 1 witness is 1- P_Bernoulli(k=1, n=10)=0.99997. We are therefore quite sure that if with 10 trials we haven’t found a witness the number is prime but we will never be 100% sure.</p><p>My implementation in code of the Miller-Rabin algorithm can be found <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/crypt.py">here</a>. Also the code to generate random prime numbers. Checking the calculation time with a regular laptop (2.6GHz 6 core 16 GB RAM) I get in between 25ms to 60ms to generate a 256 bit random prime, in between 80 and 120ms for 512 bit prime and between 500ms to 2.15s for 1024 bit prime. All this checking for 40 maximum values of potential witnesses <strong>a</strong>.</p><h3>Conclusions</h3><p>Prime numbers are the building blocks of arithmetics and are very useful in cryptography. We’ve seen how prime numbers distribute in density, how to efficiently find them and how to test if a number is prime or composite using the Miller-Rabin primality testing.</p><p><strong>Thank you for reading!</strong>. If you like the article, please star my github <a href="https://github.com/SebastiaAgramunt/Cryptography">repo</a> and give me some claps in the article.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7eab54534809" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Number theory for Cryptography and Privacy Preserving Machine Learning]]></title>
            <link>https://sebastiaagramunt.medium.com/number-theory-for-cryptography-and-privacy-preserving-machine-learning-866b1f171c51?source=rss-172fdcae7d76------2</link>
            <guid isPermaLink="false">https://medium.com/p/866b1f171c51</guid>
            <category><![CDATA[algebra]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Sebastia Agramunt-Puig]]></dc:creator>
            <pubDate>Mon, 28 Sep 2020 22:53:45 GMT</pubDate>
            <atom:updated>2020-10-10T10:11:03.525Z</atom:updated>
            <content:encoded><![CDATA[<p><em>This is a first post in which I intend to explain the basic ingredients needed to understand the cryptography for privacy preserving machine learning topics. Here I will cover number theory, for python code check this </em><a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/01_Notes_on_Number_Theory.ipynb"><em>notebook</em></a><em>.</em></p><p>Privacy preserving machine learning (PPML) is a relatively new field of study that aims to protect data privacy as well as intellectual property in the field of machine learning. It tries to solve problems like avoiding your model to retain particular information, train a model on data you cannot see or even expose a model to be used for inference whilst keeping both the original data and the prediction private.</p><p>PPML has gained interest from different academic fields like information theory and cryptography. In this post I will focus on the most basic ingredients for the latter, basic number theory. My intention is to publish a series of posts so that we can eventually understand key concepts for cryptography in machine learning and secure multiparty computation.</p><h3>Divisibility and greatest common divisor</h3><p>In this section I write about division of integer numbers. This will be used through all this post in one way or another. Given two natural numbers <strong>a</strong> and <strong>b</strong> (the latter nonzero) we say that<strong> b</strong> <em>divides</em> <strong>a</strong> if there is another integer <strong>c</strong> such that <strong>a</strong>=<strong>b</strong>*<strong>c</strong>. If, conversely we can’t find such <strong>c </strong>then if<strong> b&lt;a </strong>we can find a relation<strong> a</strong>=<strong>b*q</strong>+<strong>r </strong>where<strong> q</strong> is called quotient and<strong> r </strong>remainder.<strong> </strong>This, in other words is what we learn at primary school, just a bit more formalised.</p><p>If there’s a number <strong>d</strong> that divides both, <strong>a</strong> and <strong>b</strong>, we also say that d is a <em>common divisor</em> of <strong>a</strong> and <strong>b</strong>. For instance, 2 is a common divisor of 60 and 80 since you can write 60=30*2 and 80=40*2. One way to calculate the <em>greatest common divisor</em> (gcd) of two integers is through the <em>extended euclidean algorithm</em>: given two positive integers <strong>a</strong> and <strong>b</strong>, the following equation holds</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/176/1*PJAZjRDSOnXqc2mgLSjRAA.png" /></figure><p>The python code to solve this equation can be found <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/01_Notes_on_Number_Theory.ipynb">here</a>. For instance, the solution for the pair (a, b)=(30,27) is g, u, v = (3, 1, -1) where g is the gcd. And a last definition, <strong>a</strong> and <strong>b</strong> are said to be <em>coprime</em> iff gcd(a, b)=1, that is the largest number that divides both is 1.</p><h3>Modular arithmetic</h3><p>Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” when reaching a certain value. First we need to fix a value <strong>m </strong>and then compute the modulo over an integer<strong> a</strong>, the result is the remainder of the division. For instance, if m=7</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/127/1*bI0-s3BR-FR32hp1wZwYYA.png" /><figcaption>Applying mod m to several i values</figcaption></figure><p>you can see that the value of the operation remains the same for i&lt;m, when it reaches <strong>m</strong> it “wraps around” and begins with 0 again.</p><p>Now you may wonder… why does this have to do with cryptography? Well, there are two reasons, the first and most important is that modular arithmetic allows the construction of simple algebras like groups or fields, these are the building blocks of cryptography. The second reason is that this defines a finite set of elements (not infinite like natural numbers and real numbers) and therefore is more tractable on a computer.</p><p>The modulo operation defines an <a href="https://en.wikipedia.org/wiki/Group_(mathematics)">algebraic group</a> over the sum, so if we take the previous example of m=7, the elements of the group are (0, 1, 2, 3, 4, 5, 6) and the operation is the sum modulo m. See the “multiplication” table for operation sum modulo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/285/1*qKxyYIunG8icAAw2URybqw.png" /><figcaption>sum modulo table for group defined by m=7</figcaption></figure><p>A group has the following properties</p><ul><li><strong>Element closure</strong>: for any two elements <strong>a</strong> and <strong>b</strong> of the group, their operation returns <strong>c</strong> which is also in the group. E.g. (5+3)(mod 7)=1</li><li><strong>Associativity</strong>: for any three elements <strong>a</strong>, <strong>b</strong>, <strong>c</strong> it holds (<strong>a</strong>+<strong>b</strong>)+<strong>c</strong>=<strong>a</strong>+(<strong>b</strong>+<strong>c</strong>). This obviously happens in the sum operation.</li><li><strong>Existence of identity</strong>: There exist an element <strong>e</strong> in the set such that for any <strong>a</strong> in the set <strong>a</strong>+<strong>e</strong>=<strong>a</strong>. In this example the neutral element is 0. E.g. (5+0)(mod 7)=5.</li><li><strong>Inverse element</strong>: For any element in the group <strong>a</strong> there must be another element <strong>b</strong> such that <strong>a</strong>+<strong>b</strong>=<strong>e</strong>. E.g. the inverse of 5 is 2 in our example because (5+2)(mod 7)=0</li></ul><p>If the group is commutative (i.e. a+b=b+a), then the group is also called commutative group or abelian.</p><h4>Modulo operations on product</h4><p>The sum modulo operation works well to construct a group, just choose an <strong>m </strong>(any m of the natural numbers will work) and you will be in the realm of the numbers (0, 1, 2, …, m-1) and the modulo operation with addition. But what if instead of the sum we choose the product to define a group?. In this case the neutral element is 1 and we’ll find out that sometimes we cannot form a group for arbitrary <strong>m</strong>, for instance take <strong>m</strong>=10, are you able to find the multiplicative inverse of 2, i.e. find <strong>x </strong>such that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/171/1*BQRNawNhtudAwUjej6H2Cg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/80/1*PLwBGx0ZUqMS3nw0PwqGIg.png" /><figcaption>multiplication table for 2 in mod 10.</figcaption></figure><p>From the multiplication table you can see that there’s no number that multiplied by 2 gives the neutral multiplication number (1) in the field mod 10. We can say that these elements do not form a group because we are missing inverse elements on some (if you check it, those without inverse are 2, 4, 5, 6, 8). But good news we can pick those elements that have inverse and form a group!. Let me write a multiplication table for such group in <strong>m</strong>=10</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/188/1*InP71iQeJZ9w0utNasFybQ.png" /><figcaption>Multiplication table for the group with elements (1, 3, 7, 9) and operation product modulo 10.</figcaption></figure><p>Here you can check by eye that all elements have another element to which if multiplied give the multiplicative identity.</p><p>Now, is there a way to know if an element has inverse modulo m? <a href="https://www.springer.com/gp/book/9781441926746">Yes</a>!. Let <strong>a</strong> and <strong>m</strong> be integers such that <strong>a</strong>&lt;<strong>m</strong>, then <strong>a</strong>*<strong>b</strong> (mod <strong>m</strong>)=1 for some integer <strong>b</strong> if and only if gcd(<strong>a</strong>, <strong>m</strong>)=1. Actually we can use the extended euclidean algorithm to calculate the inverse:</p><p>If <strong>a</strong> has inverse modulo <strong>m</strong>, then from the stated above:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/118/1*QbqW3Tqb3EE1l73kFLQzRw.png" /><figcaption>Extended Euclidean equation for gcd(a, m)=1</figcaption></figure><p>by applying mod <strong>m</strong> to both sides of the equation we will have that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/62/1*of5-b1IX_FIADBeyD0knJg.png" /></figure><p>and therefore <strong>u</strong> is the inverse of <strong>a</strong> mod <strong>m</strong>. There is a special case when <strong>m</strong> is a prime number, we will denote it from now on with <strong>p</strong>. In this case, gcd(<strong>a</strong>, <strong>p</strong>)=1 since <strong>p</strong> is only divisible by himself and 1, therefore all the elements (1, 2, 3, …, p-1) will have inverse and will form a group with the product modulo <strong>p</strong>. An easy way to calculate the multiplicative inverse in a prime modulo group is to use the Fermat’s little theorem: Let <strong>p</strong> be a prime number and let <strong>a</strong> be any integer then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/151/1*G3fTvph9GbCjSzV-a6nT6g.png" /><figcaption>Fermat’s little theorem for a not divisible by p</figcaption></figure><p>if <strong>a</strong> is not divisible by <strong>p</strong>, otherwise the above equation equals zero. Then to calculate the inverse of <strong>a</strong>, we just need to multiply by <strong>a</strong>^(-1) both sides of the equation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/172/1*Wuk6KCfL3-d7Bf51wgu4Mg.png" /><figcaption>Multiplicative inverse of a for a mod p field</figcaption></figure><p>so we can now calculate the inverse modulo <strong>p </strong>of<strong> a</strong>. This may seem heavy computationally but we use the fast powering algorithm an implementation of which can be found <a href="https://github.com/SebastiaAgramunt/Cryptography/blob/master/notebooks/crypt.py#L135">here</a>.</p><h3>Rings and Fields</h3><p>So far we’ve seen how to to define mathematical groups with sum and multiplication modulo an integer <strong>m</strong>. We can construct other algebraic structures using both operations. A ring is an algebraic structure consisting of a set of elements S and two operations (+, ·) that fulfil the following properties</p><ul><li>The set with the first operation form an abelian group. i.e. (S, +) is abelian</li><li>There’s associativity on the second operation. I.e. if <strong>a</strong>, <strong>b</strong>, <strong>c</strong> are elements of S then (<strong>a</strong>·<strong>b</strong>)·<strong>c</strong>=<strong>a</strong>·(<strong>b</strong>·<strong>c</strong>).</li><li>Existence of identity on the second operation. I.e. there exist an element <strong>e</strong> such that for any <strong>a</strong> in the set <strong>a</strong>·<strong>e</strong>=<strong>a</strong>.</li><li>The second operation is distributive with respect to the first one. This is <strong>a</strong>·(<strong>b</strong>+<strong>c</strong>)=<strong>a</strong>·<strong>b</strong>+<strong>a</strong>·<strong>c</strong> and (<strong>b</strong>+<strong>c</strong>)·<strong>a</strong>=<strong>b</strong>·<strong>a</strong>+<strong>c</strong>·<strong>a</strong></li></ul><p>The set <strong>S</strong>={0, 1, 2, 3} with the modular operations of additions (+ mod 4) and multiplications (· mod 4) is a ring. Another example of ring is the set of matrices of dimension 3x3 and real coefficients. You can check that all properties above are accomplished (takehome exercise)</p><p>A field is a ring such that the second operation also satisfies all the abelian group properties (after throwing out the identity element of the first operation). The field has multiplicative inverses, multiplicative identity and is commutative.</p><p>A typical example of field is the set S={0, 1, 2, 3, …, <strong>p</strong>} where <strong>p</strong> is a prime number and operations are addition and multiplication modulo <strong>p</strong>. See that since <strong>p</strong> is a prime all the elements of the set have a multiplicative inverse and therefore constitute an abelian group with the multiplication operation. This field is commonly denoted as <strong>Fp</strong>. The set of matrices with dimension 3x3 and real coefficients is not a field since some matrices do not have a multiplicative inverse.</p><h3>Conclusions</h3><p>We understood what is modulo arithmetic and how with such operation we can define groups, rings and fields over finite sets of elements. These structures appear constantly in cryptography, for instance when working with elliptic curves or in simple protocols like Diffie-Hellman key exchange.</p><p>In the next posts we are going to work with the defined algebraic structures to understand key concepts on cryptography and multiparty computation to the final end of understanding a bit more of privacy preserving machine learning.</p><p><strong>Thank you for reading!</strong>. If you like the article, please star my github <a href="https://github.com/SebastiaAgramunt/Cryptography">repo</a> and give me some claps in the article.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=866b1f171c51" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>