Solving Cryptography Problems - 3

Here’s the next problem:

The public key is $N=209$. What is the Rabin decryption of $80$?

  • What is Rabin decryption?
    wikipedia: The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA.

  • What is a chosen plaintext attack?
    wikipedia: A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts. The goal of the attack is to gain information that reduces the security of the encryption scheme.

  • How does the Rabin Encryption scheme work?
    wikipedia: The keys for the Rabin cryptosystem are generated as follows:
    1. Choose two large distinct prime numbers $p$ and $q$ such that $p\equiv 3\bmod 4$ and $q\equiv 3\bmod 4$.
    2. Compute $n=pq$. Then $n$ is the public key and the pair $(p,q)$ is the private key.
  • Decryption
    Since 209 is not a large number, we can easily factorise it through trial and error:
i = 2
while 209 % i != 0: i+=1
print(i, 209/i)

11 19.0

Let $p=11$ and $q=19$. Now, following the procedure from wikipedia,

The message $m$ can be recovered from the ciphertext $80$ by taking its square root modulo $209$ as follows.

  1. Compute the square root of $c$ modulo $p$ and $q$:

    \[m_p = 80^{\frac{1}{4}(11+1)} \bmod{11} = 5 \\ m_q = 80^{\frac{1}{4}(19+1)} \bmod{19} = 17\]
  2. Using the extended Euclidean algorithm to find $y_p$ and $y_q$ such that

    \[y_p \cdot p + y_q \cdot q = 1\]
     def ExtEuclid (a,b):
     # returns a triple (d,s,t) such that d = gcd(a,b) and
     # d == a*s + b*t
     if b == 0: return (a,1,0)
     (d1, s1, t1) = ExtEuclid(b,a%b)
     d = d1
     s = t1
     t = s1 - int(a / b) * t1
     return (d,s,t)
    
     print('{} = 19*({}) + 11*({})'.format(*ExtEuclid(19,11)))
    

    1 = 19(-4) + 11(7)

    So we have $y_p = 7$ and $y_q = -4$.
    These two articles (this one and this one) were useful in understanding the algorithm.

  3. Using the Chinese remainder theorem to find the four square roots of $c$ modulo $n$: \(r_1 = (7 \cdot 11 \cdot 17 + (-4) \cdot 19 \cdot 5) \bmod 209 = 93\\ r_2 = 209 - 93 = 116\\ r_3 = (7 \cdot 11 \cdot 17 - (-4) \cdot 19 \cdot 5) \bmod 209 = 17\\ r_4 = 209 - 17 = 192\)

    One of these four values is the original plaintext $m$, although which of the four is the correct one cannot be determined without additional information.
    Of these four, $93$ is the only value that matches an option in my assignment, which means that it is the original plaintext in this case.

Further Reading / Questions:

Here’s the next one:

The public key is $N = 713$. What is the Rabin Digital Signature of $473$?

  • What is the Rabin Signature Scheme?
    From my class notes,
    Signature: $s = m^{1/2} \bmod n$ where $s$ is the signature
    Verification: $m = s^2 \bmod n$

Now I can think of two ways to solve this:

  • the one where we use pen and paper

    $x^2 \equiv 473 \bmod 713$
    $\implies x^2 \equiv 473 \bmod 23$ and $x^2 \equiv 473 \bmod 31$
    $\implies x^2 \equiv 13 \bmod 23$ and $x^2 \equiv 8 \bmod 31$
    $\implies x^2 \equiv 36 \bmod 23$ and $x^2 \equiv 225 \bmod 31$
    $\implies x \equiv \pm 6 \bmod 23$ and $x \equiv \pm 15 \bmod 31$

    We can then solve the four sets of equations using the Chinese Remainder theorem. These two videos (this one and this one) helped me in this approach.

  • the one where we use a brute force approach

      i = j = 1
      while j <= 4:
          while i**2 % 713 != 473: i+=1
          print(i)
          i+=1
          j+=1
    

Either way, the four roots we get are: $109$, $201$, $512$ and $604$.

Of these four, $201$ is the only one present in the given options in my assignment, so that is the solution to this problem.

Further Reading / Questions:

I clearly need to read more about Rabin’s cryptosystem, because the knowledge I have currently is not complete. I don’t want to make any commitments, except that if I encounter it again I’ll try to gain an in depth understanding of the cryptosystem and the problem solving techniques it involves (such as the Chinese remainder theorem).

Until next time!




Solving Cryptography Problems - 2

Following up from my previous post, here’s the next problem:

The public key is $(n, e) = (221, 11)$. What is the RSA Decryption of $7$?

  • What is RSA? wikipedia: RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and distinct from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the “factoring problem”.

  • How does RSA work?
    Let’s look at an example from wikipedia:

  1. Choose two distinct prime numbers, such as
    $p = 61$ and $q = 53$
  2. Compute $n = pq$ giving
    $n = 61 \times 53 = 3233$
  3. Compute the Carmichael’s totient function of the product as
    $\lambda (n)=\operatorname {lcm} (p-1,q-1)$ giving
    $\lambda (3233)=\operatorname {lcm} (60,52)=780$
  4. Choose any number $1 \lt e \lt 780$ that is coprime to $780$. Choosing a prime number for $e$ leaves us only to check that $e$ is not a divisor of $780$. Let $e = 17$.
  5. Compute $d$, the modular multiplicative inverse of $e \bmod \lambda(n)$ yielding, $d = 413$
    Worked example for the modular multiplicative inverse:
    $d\times e \equiv 1{\bmod {\lambda }}(n)$
    $413\times 17 \equiv 1{\bmod {7}}80$

The public key is $(n = 3233, e = 17)$. For a padded plaintext message m, the encryption function is $c(m)=m^{17} \bmod 3233$

The private key is $(n = 3233, d = 413)$. For an encrypted ciphertext c, the decryption function is $m(c)=c^{413} \bmod 3233$

For this problem we have $n$, $e$, and $c$. We have to find $d$ and calculate $m$ using the above decryption function.
$n = 221 = 13 \times 17$. Carmichael’s totient function, $\lambda (221)=\operatorname {lcm} (12,16)=48$. We already have $e = 11$.
$d$ is the modular multiplicative inverse of $e \bmod \lambda(n)$ i.e.,
$d \times e \equiv 1 \bmod \lambda (n)$ or $d \times 11 \equiv 1 \bmod 48$.

We can write a simple program to calculate d:

d = 0
while (11 * d) % 48 != 1: d+=1
print(d)

35

Now we can find $m$ as: $m = c ^ d \bmod n = 7 ^{35} \bmod 221 = 54$

Thus, 54 is our final answer.

Further reading:

  • What is Carmichael’s totient function?
    wikipedia: The Carmichael function associates to every positive integer $n$ a positive integer $\lambda (n)$, defined as the smallest positive integer $m$ such that
    \(a^m \equiv 1 \bmod n\)
    for every integer $a$ between $1$ and $n$ that is coprime to $n$.

wikipedia: The exponent of the multiplicative group of integers mod n (previous post), that is, the least common multiple of the orders in the cyclic groups, is given by the Carmichael function $\lambda (n)$. In other words, $\lambda (n)$ is the smallest number such that for each $a$ coprime to $n$, $a^{\lambda(n)} \equiv 1 \pmod n$ holds.

  • How can we find the modular multiplicative inverse using pen and paper? By making use of the Extended Euclidean Algorithm. Here’s a youtube video that walks you through the procedure and here’s a Khan Academy article that explains it well. Adding these here for myself for future reference.

Now let’s try another one:

The public key is $(n, e) = (437, 13)$. What is the RSA Digital Signature of $17$?

  • What is RSA Digital Signature?
    This article explained it very well. From the article, here is the “textbook” definition of RSA signing compared with the Encryption and Decryption functions.

    • $Enc(m; e) = R(m,e)$
    • $Dec(c; d) = R(c,d)$
    • $Sign(m; d) = R(m,d)$
    • $Ver(m; s; e) = R(s,e) == m$

We are basically applying the sender’s private key on the message they are sending to generate a signature. That means, for this problem, we have to find $m^d \bmod n$.

We can follow the procedure from the previous problem now. $d$, or the private key, is the modular multiplicative inverse of $e \bmod \lambda (n)$. Here, $\lambda (n)$ is the Carmichael totient function, calculated as $\lambda (n) = lcm (p-1, q-1)$, where $p$ and $q$ are the prime factors of $N$.

Through trial and error, we find that the prime factors of $n = 437$ are $19$ and $23$. Of course this would be a very difficult problem if the prime numbers were sufficiently large; that’s the whole idea behind RSA encryption. Anyways, now that we have $p$ and $q$, we can find $\lambda (437) = lcm (18, 22) = 198$. Now, using the same algorithm I used for the previous problem,

d = 0;
while (d * 13) % 198 != 1: d+=1
print(d)

61

Therefore, the solution to this problem is $17^{61}\bmod 437 = 195$.

Until next time!




Solving Cryptography Problems - 1

Following the “solving a mystery” approach from my last post, I will be attempting to solve a couple of problems from my Cryptography Assignment.

Here’s the first one:

Let $\small G : \{0,1\}^4 \to \{0,1\}^4 $ be a 4-bit block cipher defined by $ G(x_1 x_2 x_3 x_4) = x_4 x_2 x_3 x_1 $. What is the CBC-MAC of $ 10100101 $?

It looks like $G$ is a function that takes a 4-bit binary number (a “nibble”) as input and gives another nibble as output. From the definition, it seems that if I give $0001$ as input, I will get $G(0001) = 1000$ as output.

  • What is a block cipher?
    wikipedia: In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key.

  • what is a deterministic algorithm?
    wikipedia: A deterministic algorithm computes a mathematical function. In other words, given a particular input, the algorithm will always produce the same output, with the underlying machine always passing through the same sequence of states.

So in this case, $G$ is the deterministic algorithm. Now, given $G$, we have to find the CBC-MAC of $ 10100101 $.

  • What is a CBC-MAC?
    wikipedia: A cipher block chaining message authentication code (CBC-MAC) is a technique for constructing a message authentication code from a block cipher. The message is encrypted with some block cipher algorithm in CBC mode to create a chain of blocks such that each block depends on the proper encryption of the previous block.

  • What is a message authentication code?
    wikipedia: A message authentication code (MAC), sometimes known as a tag, is a short piece of information used to authenticate a message—in other words, to confirm that the message came from the stated sender (its authenticity) and has not been changed.

    Informally, a message authentication code system consists of three algorithms:

    • A key generation algorithm selects a key from the key space uniformly at random.
    • A signing algorithm efficiently returns a tag given the key and the message.
    • A verifying algorithm efficiently verifies the authenticity of the message given the key and the tag. That is, return accepted when the message and tag are not tampered with or forged, and otherwise return rejected.
  • What is the CBC mode for a block cipher algorithm?
    wikipedia: In CBC mode, each block of plaintext is XORed with the previous ciphertext block before being encrypted. This way, each ciphertext block depends on all plaintext blocks processed up to that point. To make each message unique, an initialisation vector must be used in the first block.

We have to find the CBC-MAC of $ 10100101 $. Upon breaking it into blocks of 4-bits, we get $ 1010 $ and $ 0101 $.

  • What should the initialisation vector be when calculating CBC-MAC?
    wikipedia: To calculate the CBC-MAC of message m, one encrypts m in CBC mode with zero initialization vector and keeps the last block.

$ G(0000 \oplus 1010) = G(1010) = 0011 $
$ G(0011 \oplus 0101) = G(0110) = 0110 $

The last block is the CBC-MAC. Thus, $ 0110 $ is the solution of this problem.

That was fun. Let’s try another one:

Alice and Bob are following the Diffie–Hellman Secret Key Exchange Protocol with $p = 101$ (the prime number $p$), $g=2$ (the generator of $\mathbb{Z}^*_p$), $x=11$ (the private key of Alice), $y=13$ (the private key of Bob). What is the shared secret key between Alice and Bob?

  • What is the Diffie–Hellman Secret Key Exchange Protocol ?
    I already have an idea about this protocol from this Coursera course. Here is an example from Wikipedia:

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1. Here is an example of the protocol

  1. Alice and Bob publicly agree to use a modulus $p = 23$ and base $g = 5$ (which is a primitive root modulo 23).
  2. Alice chooses a secret integer $a = 4$, then sends Bob $A = g^a \bmod p$
    • $A = 5^4 \bmod 23 = 4$
  3. Bob chooses a secret integer $b = 3$, then sends Alice $B = g^b \bmod p$
    • $B = 5^3 \bmod 23 = 10$
  4. Alice computes $s = B^a \bmod p$
    • $s = 10^4 \bmod 23 = 18$
  5. Bob computes $s = A^b \bmod p$
    • $s = 4^3 \bmod 23 = 18$
  6. Alice and Bob now share a secret (the number 18).

Let’s apply the above procedure to this problem.

  1. Alice and Bob publicly agree to use a modulus $p = 101$ and base $g = 2$ (which is a primitive root modulo 101).
  2. Alice chooses a secret integer $a = 11$, then sends Bob $A = g^a \bmod p$
    • $A = 2^{11}\bmod101 = 28$
  3. Bob chooses a secret integer $b = 13$, then sends Alice $B = g^b \bmod p$
    • $B = 2^{13}\bmod101 = 11$
  4. Alice computes $s = B^a\bmod p$
    • $s = 11^{11}\bmod101 = 86$
  5. Bob computes $s = A^b\bmod p$
    • $s = 28^{13}\bmod101 = 86$
  6. Alice and Bob now share a secret (the number 86).

Hence, the solution of this problem is 86. Here’s some additional information:

  • What is a primitive root modulo?
    wikipedia: $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$, there is an integer $k$ such that $g^k \equiv a \bmod n$. Note that $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$.

  • What is the multiplicative group of integers modulo $n$?
    wikipedia: The integers coprime (relatively prime) to $n$ from the set $\{0,1,\dots ,n-1\}$ of n non-negative integers form a group under multiplication modulo $n$, called the multiplicative group of integers modulo $n$.

  • What is a group (algebra)?
    wikipedia: A group is a set equipped with a binary operation that combines any two elements to form a third element in such a way that four conditions called group axioms are satisfied, namely closure, associativity, identity and invertibility.

So, an example of a multiplicative group of integers modulo n might be \((\mathbb{Z}_5^*, *)\) where $\mathbb{Z}_5^* = \{x : gcd(x, 5) = 1\}$ i.e. $\mathbb{Z}_5^* = \{1, 2, 3, 4\}$ and $a * b = ab \bmod 5$. We can verify that the four group axioms are satisfied. I’ll go into more detail if a future problem requires me to do so. For now, I’ll end here.




Math is Fiction

3b1b said in his TED talk that Math is like a Mystery story. I’ll be trying to solve a question today with very little prior knowledge and will be listing out my thought process and internet search history.

If the extremal of the functional

\[I[y(x)] = \int_{0}^{2}\frac{(y')^2}{x}dx\]

subject to the conditions $y(0) = \alpha$, $y(2) = \beta$ is a parabola passing through the origin, find the values of $\alpha$ and $\beta$ .

the problem +--> extremal +--> smooth functions
            |             +--> Euler equations
            |             +--> extremum conditions
            |             +--> variational calculus
            |
            +--> functional
            +--> calculus of variations +--> Euler-Lagrange equation +--> solving second order partial differential equations

what is an extremal?

  • A smooth solution of the Euler equation, which is a necessary extremum condition in the problem of variational calculus.

a solution must be a function
what is a smooth function?

  • my knowledge: a function that is infinitely differentiable
  • wikipedia: In mathematical analysis, the smoothness of a function is a property measured by the number of continuous derivatives it has over some domain. At the very minimum, a function could be considered “smooth” if it is differentiable everywhere (hence continuous). At the other end, it might also possess derivatives of all orders in its domain, in which case it is referred to as a C-infinity function (or $C^\infty$ function).

what is the Euler equation?

  • nasa: The Euler Equations describe how the velocity, pressure and density of a moving fluid are related. They are a set of coupled differential equations and they can be solved for a given flow problem by using methods from calculus. (added later:) The equation we’re concerned with is the Euler-Lagrange equation.

what is an extremum condition?

  • my knowledge: one of the conditions for which a function attains it’s maximum or minimum value in it’s domain (or a given range)

what is variational calculus?

  • wikipedia: The calculus of variations is a field of mathematical analysis that uses variations, which are small changes in functions and functionals, to find maxima and minima of functionals: mappings from a set of functions to the real numbers.

Cool, now we also know what functionals are. In a little more detail,

  • wikipedia: In mathematics and computer science, a higher-order function is a function that does at least one of the following:
    • takes one or more functions as arguments (i.e. procedural parameters),
    • returns a function as its result. All other functions are first-order functions. In mathematics higher-order functions are also termed operators or functionals. The differential operator in calculus is a common example, since it maps a function to its derivative, also a function. NOTE: (added later) functionals != higher order functions.

wow, we also have functionals in some programming languages!
Here’s an example in java:

Function<IntUnaryOperator, IntUnaryOperator> twice = f -> f.andThen(f);
twice.apply(x -> x + 3).applyAsInt(7); // 13

what’s the difference between a functional and a composite function?

  • stackexchange: Composition of functions is when you “feed” the result of one function into another function to produce yet a third function. A functional, on the other hand, is when you “feed” a function – a whole function, not just the value of the function at a specific point – into some kind of “machine” that assigns a single numerical value to it. An example is a definite integral. Notice that when you apply a functional to a function, the result is a single number. That’s what is meant by the statement that the value of F(f) depends, in some sense, on the “entirety” of f(x) in a particular domain.

For example, here are some examples of functionals:

  • $F(f)=\int_{0}^{6} f(x)dx$. For $f(x)=x^2$, we’d have that $F(f)=72$.
  • $G(f)=max \{ f(x) \vert −5\le x\le 3 \} $. For $f(x)=x^2$, we’d have that $G(f)=25$.
  • $H(f)=$ the number of critical points of $f(x)$ on $[−5,3]$. For $f(x)=x^2$, we’d have $H(f)=1$.

Notice also that in each of these examples the definition of the functional requires some choice of interval; different choices would lead to different results. Finally, a particular functional may only be defined for certain classes of functions; for example, neither of the examples F and G above are not defined for a discontinuous function with a vertical asymptote at $x=2$. So in defining a function, one usually needs to limit one’s attention to some category of “nice” or “good” functions on which the functional will operate.

(reference: mweiss https://math.stackexchange.com/users/124095/mweiss, What is the difference between a functional and a composite function?, URL (version: 2018-06-29): https://math.stackexchange.com/q/2836265)

Turns out that the wikipedia example was for higher order functions, not functionals. A differential operator alone is not a functional. A differential operator when also evaluated at a point is a functional.

The problem is starting to make more sense now. We have been given a functional

\[I[y(x)] = \int_{0}^{2}\frac{(y')^2}{x}dx\]

So if I have $y(x) = x^2$, the output of my functional will be 2, i.e. $I[x^2] = 2$. Okay. The problem says that the extremal of this functional, i.e., the input function that gives the maximum or minimum value is a parabola that passes through the origin. If $e(x)$ is the extremal for the functional, we have to find $e(0)$ and $e(2)$. But wait a second. If the extremal function passes through the origin, shouldn’t $e(0) = 0$? Well, that was easy. So we just have to find $e(2)$ now.

how to find the extremal of a functional?

Euler-Lagrange equation derivation

  • this video explains it pretty well. The derivation is very smart, I was impressed!

We assume $y(x)$ to be an extremal of the functional

\[I = \int_{x1}^{x2} f(x, y(x), y'(x)) \tag{i}\]

We also have the boundary conditions for the curve $y(x)$: $y(x_1) = y_1$ and $y(x_2) = y_2$. Then, we consider all the curves that have the same boundary conditions, that is, the family of curves to which $y(x)$ belongs,

\[z(x) = y(x) + \epsilon \eta (x) \tag{ii}\]

where, $\eta(x)$ is an arbitrary function such that $\eta(x1) = \eta(x2) = 0$ and $\epsilon$ is an arbitrary constant. Okay. Now, when we put the function $z(x)$ into the functional $I$, it should return a single value, right? Yes. It does exactly that. This value is in terms of $\epsilon$. If you look carefully at the equation of the family of curves, you will notice that $z(x)$ will be an extremal of $I$ when $\epsilon = 0$. Therefore, we have, $\left.\frac {dI}{d\epsilon}\right|_0 = 0$. Thus, we can put in the RHS of $(i)$ into this equation and get the condition for an input function to be an extremal (refer to the video for the calculations) and we end up with the Euler-Lagrange equation:

\[\frac {\delta f}{\delta y} - \frac {d}{dx}\left(\frac{\delta f}{\delta y\,'}\right) \tag{iii}\]

Let’s get back to the problem. We put the function $e(x) = \frac{(y\,’)^2}{x}$ into the Euler-Lagrange equation, and we get the following second order differential equation:

\[e\,'' - \frac {e\,'}{x} = 0 \tag{iv}\]
  • how to solve a second order differential equation found this pdf

substitute $e\,’$ for some $u$ and solve like a first order differential equation. The solution we get is:

\[e(x) = mx^2 + n\]

where m and n are real constants.

using the boundary conditions, we get that $e(2) = \beta = 4m$, that is $\beta \in \mathbb{R}$ and we already know that $\alpha = 0$. The problem has been solved.

Phew! I must admit it, I did not think this would take me an entire day to solve. Anyways, treating this problem like a mystery story allowed me to enjoy the entire process.




Baby Steps

This post is a part of a series of posts related to my Google Summer of Code ‘20 project.

The past week, I worked on the GUI part of the add-on, which is simply two dialog boxes. These dialog boxes allow the user to specify the location of a GraphQL schema and corresponding endpoint. I also read up on some GraphQL concepts.

Listing all GraphQL data types

I read the GraphQL documentation on ‘Schemas and Types’ which had a good explanation of the GraphQL type system. Here’s a flow chart I created that lists all GraphQL data types:

Types +--> Object Types +--> Regular Objects
      |                 +--> "Entry Points" +--> Queries
      |                                     +--> Mutations
      |
      +--> Scalar Types +--> Int
      |                 +--> Float
      |                 +--> String
      |                 +--> Boolean
      |                 +--> ID
      |               
      +--> Enumeration Types
      +--> Abstract Types +--> Interfaces
                          +--> Unions

You can click here for a more visual representation.

Creating Import Dialogs

The code for the import dialogs is very similar to the dialogs from the openapi add-on, with some changes to allow the omission of the schema file path/URL. These changes were necessary because GraphQL endpoints have a neat feature called Introspection that enables us to ask them for information about what queries the schema supports.

There were also some changes in the validation of URLs. For that, I took hints from the quickstart add-on. To add a URL into the sites tree, I looked at the code from the openapi and soap add-ons.

You can find the code for the import dialogs in my most recent pull request (#2420).

Creating a Simple Example

I also experimented with graphql-java and it’s getting started tutorial.

Plans for this Week

After a video call with my mentors today, I now have a clear view of the big picture and the work that I have to do. The first stage of the add-on is ZAP being able to understand an imported schema and generate all possible requests from it. Once the sites tree has been populated, then we will move on to attacks / active scan rules.

For now, these are the things I have to begin working on:

  • importing a schema from a file
  • importing a schema from a URL
  • importing a schema from a URL via Introspection
  • a spider that finds endpoint URLs
  • a parser that understands a schema and generates queries from it

By the way, the title of this post comes from an anime that I watched a while ago. It’s about a boy called Maruo Eiichirou who learns to play tennis by taking extensive notes. I found it to be a little slow, but quite motivating. You can check it out here.