math_prequisites.tex 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302
  1. \chapter{Mathematical prequisites \label{chap:preq}}
  2. In this chapter we formalize the notation used in the rest of the thesis, and
  3. furthermore attempt to discuss and study the elementary functions on which the
  4. project has been grounded.
  5. \\
  6. The $\ll$ and $\gg$ are respectively used with the meaning of left and right
  7. bitwise shift, as usual in computer science.
  8. \\
  9. The $\dsqrt$ function will be defined in section \ref{sec:preq:sqrt}, with the
  10. acceptation of discrete square root.
  11. \\
  12. The logarithmic $\log$ function is assumed to be in base two, i.e. $\log_2$.
  13. \\
  14. The $\idiv$ symbol is the integer division over $\naturalN$, i.e.
  15. $a \idiv b = \floor{\frac{a}{b}}$, as usual in the python language.
  16. \\
  17. $\naturalPrime \subset \naturalN$ is the set containing all prime intgers.
  18. \\
  19. The binary operator $\getsRandom$, always written as $x \getsRandom S$, has the
  20. meaning of ``pick a uniformly distributed random element $x$ from the set $S$''.
  21. % XXX. following Dan Boneh notation
  22. \section{Algorithmic Complexity Notation}
  23. The notation used to describe asymptotic complexity follows the $O$-notation,
  24. abused under the conventions and limits of MIT's Introduction to Algorithms
  25. \cite{MITalg}.
  26. Let \bigO{g} be the asymptotic upper bound of g:
  27. $$
  28. \bigO{g(n)} = \{ f(n) : \exists n_0, c \in \naturalN \mid 0 \leq f(n) \leq cg(n)
  29. \ \forall n > n_0 \}
  30. $$
  31. With $f(n) = \bigO{g(n)}$ we actually mean
  32. $f(n) \in \bigO{g(n)}$.
  33. \section{Euclid's Greatest Common Divisor \label{sec:preq:gcd}}
  34. Being the greatest common divisor a foundamental algebraic operation in the TLS
  35. protocol, \openssl implemented it with the following signature:
  36. \begin{minted}[fontsize=\small]{c}
  37. int BN_gcd(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx);
  38. \end{minted}
  39. The computation proceeds under the well-known Euclidean algorithm, specifically
  40. the binary variant developed by Josef Stein in 1961 \cite{AOCPv2}. This variant
  41. exploits some interesting properties of $gcd(a, b)$:
  42. \begin{itemize}
  43. \setlength{\itemsep}{1pt}
  44. \setlength{\parskip}{0pt}
  45. \setlength{\parsep}{0pt}
  46. \item if $a,\ b$ are even, then $gcd(a, b) = 2gcd(a/2, b/2)$;
  47. \item if $a$ is even and $b$ is odd, then $gcd(a, b) = gcd(a/2, b)$;
  48. \item $gcd(a, b) = gcd(a-b, b)$, as in the standard Euclid algorithm;
  49. \item the sum of two odd numbers is always even.
  50. \end{itemize}
  51. % Donald Knuth, TAOCP, "a binary method", p. 388 VOL 2
  52. Both \cite{AOCPv2} and \cite{MITalg} analyze the running time of the
  53. algorithm; \cite{MITalg}'s proof is fairly simpler and proceeds %elegantly
  54. by induction.
  55. Anyway, both show that algorithm ~\ref{alg:gcd} belongs to the class
  56. \bigO{\log b}.
  57. \begin{algorithm}[H]
  58. \caption{\openssl's GCD \label{alg:gcd}}
  59. \begin{algorithmic}[1]
  60. \State $k \gets 0$
  61. \While{$b \neq 0$}
  62. \If{$a$ is odd}
  63. \If{$b$ is odd}
  64. \State $a \gets (a-b) \gg 1$
  65. \Else
  66. \State $b \gets b \gg 1$
  67. \EndIf
  68. \If{$a < b$} $a, b \gets b, a$ \EndIf
  69. \Else
  70. \If{$b$ is odd}
  71. \State $a \gets a \gg 1$
  72. \If{$a < b$} $a, b \gets b, a$ \EndIf
  73. \Else
  74. \State $k \gets k+1$
  75. \State $a, b \gets a \gg 1, b \gg 1$
  76. \EndIf
  77. \EndIf
  78. \EndWhile
  79. \State \Return $a \ll k$
  80. \end{algorithmic}
  81. \end{algorithm}
  82. Unfortunately, there is yet no known parallel solution that significantly improves
  83. Euclid's \textsc{gcd}.
  84. \section{Square Root \label{sec:preq:sqrt}}
  85. Computing the square root is another important building block of the project,
  86. though not available in \openssl\!.
  87. Apparently,
  88. % \openssl is a great pile of crap, as phk states
  89. \openssl does only provide the discrete square root implementation using the
  90. Tonelli/Shanks algorithm, which specifically solves in $x$ the equation
  91. $x^2 = a \pmod{p}$, with $p \in \naturalPrime$:
  92. \begin{minted}{c}
  93. BIGNUM* BN_mod_sqrt(BIGNUM* x, const BIGNUM* a, const BIGNUM* p,
  94. const BN_CTX* ctx);
  95. \end{minted}
  96. Instead, we are interested in finding the the pair
  97. $\angular{x, r} \in \naturalN^2 \mid x^2 + r = n$, that is, the integer part of
  98. the square root of a natural number and its rest.
  99. Hence, we did come out with our specific implementation, first using Bombelli's
  100. algorithm, and later with the one of Dijkstra. Both are going to be discussed
  101. below.
  102. Unless otherwise specified, in the later pages we use $\sqrt{n}$ with the
  103. usual meaning ``the half power of $n$'', while with $x, r = \dsqrt{n}$ we mean
  104. the pair just defined.
  105. \paragraph{Bombelli's Algorithm \label{par:preq:sqrt:bombelli}} dates back to
  106. the XVI century, and approaches the problem of finding the square root by using
  107. continued fractions. Unfortunately, we weren't able to fully assert the
  108. correctness of the algorithm, since the original document
  109. ~\cite{bombelli:algebra} presents a difficult, inconvenient notation. Though,
  110. for completeness' sake, we report in table
  111. ~\ref{alg:sqrt:bombelli} the pseudocode adopted and tested for its correctness.
  112. \begin{algorithm}[H]
  113. \caption{Square Root: Bombelli's algorithm}
  114. \label{alg:sqrt:bombelli}
  115. \begin{algorithmic}[1]
  116. \Procedure{sqrt}{$n$}
  117. \State $i, g \gets 0, \{\}$
  118. \While{$n > 0$}
  119. \State $g_i \gets n \pmod{100}$
  120. \State $n \gets n // 100$
  121. \State $i++$
  122. \EndWhile
  123. \State $x, r \gets 0, 0$
  124. \For{$j \in \; [i-1..0]$}
  125. \State $r = 100r + g_i$
  126. \For{$d \in \; [0, 9]$}
  127. \State $y' \gets d(20x + d)$
  128. \If{$y' > r$} \textbf{break}
  129. \Else \ \ $y \gets y'$
  130. \EndIf
  131. \EndFor
  132. \State $r \gets r - y$
  133. \State $x \gets 10x + d - 1$
  134. \EndFor
  135. \State \Return $x, r$
  136. \EndProcedure
  137. \end{algorithmic}
  138. \end{algorithm}
  139. For each digit of the result, we perform a subtraction, and a limited number of
  140. multiplications. This means that the complexity of this solutions belongs to
  141. \bigO{\log n \log n} = \bigO{\log^2 n}.
  142. \begin{remark}
  143. Note that Bombelli actually has found a solution in $x$ for a slightly
  144. different equation than the one we initially formulated. Specifically, he
  145. found the pair $\angular{x, r}$ such that $(x+r)^2=a$, where $x$ is the mantissa,
  146. while $r$ is the decimal part. For our purpose this change is irrelevant: we
  147. just need to be able to distinguish perfect squares, and thus assert that $r$
  148. is nonzero.
  149. \end{remark}
  150. \paragraph{Dijkstra's Algorithm \label{par:preq:sqrt:dijkstra}} can be found in
  151. \cite{Dijkstra:adop}, \S 8, p.61. There, Dijkstra presents an elightning
  152. process for the computation of the square root, making only use of binary shift
  153. and algebraic additions.
  154. Specifically, the problem attempts to find, given a natual $n$, the integer $a$
  155. that establishes:
  156. \begin{align}
  157. \label{eq:preq:dijkstra_problem}
  158. a^2 \leq n \: \land \: (a+1)^2 > n
  159. \end{align}
  160. Take now the pair $\angular{a=0, b=n+1}$, and consider the inverval
  161. $[a, b[$. We would like to reduce the distance between the upper bound $b$ and
  162. the lower bound $a$, while holding the guard \ref{eq:preq:dijkstra_problem}:
  163. \begin{align*}
  164. a^2 \leq n \: \land \: b > n
  165. \end{align*}
  166. %% XXX. I am not so sure about this, pure fantasy.
  167. The speed of convergence is determined by the choice of the distance $d$, which
  168. analougously to the dicotomic search problem, is optimal when
  169. $d = (b-a) \idiv 2$.
  170. \begin{algorithm}[H]
  171. \caption{Square Root: an intuitive, na\"ive implementation}
  172. \label{alg:sqrt:dijkstra_naif}
  173. \begin{algorithmic}[1]
  174. \State $a, b \gets 0, n+1$
  175. \While{$a+1 \neq b$}
  176. \State $d \gets (b-a) \idiv 2$
  177. \If{$(a+d)^2 \leq n$}
  178. $a \gets a+d$
  179. \ElsIf{$(b-d)^2 > n$}
  180. $b \gets b-d$
  181. \EndIf
  182. \EndWhile
  183. \State \Return a
  184. \end{algorithmic}
  185. \end{algorithm}
  186. % heh, there's not much to explain here, that's almost the same in Dijkstra's
  187. % book, excluding the inspirative familiar portrait that led to the insight of
  188. % this change of varaibles.
  189. Now optimization proceeds with the following change of variables:
  190. $c = b-a$,
  191. $p = ac$,
  192. $q = c^2$,
  193. $r = n-a^2$;
  194. For any further details and explainations, the reference is still
  195. \cite{Dijkstra:adop}.
  196. \begin{algorithm}[H]
  197. \caption{Square Root: final version}
  198. \label{alg:sqrt:dijkstra}
  199. \begin{algorithmic}[1]
  200. \State $p, q, r \gets 0, 1, n$
  201. \While{$q \leq n$} $q \gets q \gg 2$ \EndWhile
  202. \While{$q \neq 1$}
  203. \State $q \gets q \ll 2$
  204. \State $h \gets p+q$
  205. \State $p \gets q \ll 1$
  206. \State $h \gets 2p + q$
  207. \If{$r \geq h$} $p, r \gets p+q, r-h$ \EndIf
  208. \EndWhile
  209. \State \Return p
  210. \end{algorithmic}
  211. \end{algorithm}
  212. A fair approximation of the magnitude of the Dijkstra algorithm can be studied
  213. by looking at the pseudocode in ~\ref{alg:sqrt:dijkstra_naif}. Exactly as in
  214. the dicotomic search case, we split the interval $[a, b]$ in half on each step,
  215. and choose whether to take the leftmost or the rightmost part. This results in
  216. $log(n+1)$ steps. During each iteration, instead, as we have seen in
  217. ~\ref{alg:sqrt:dijkstra} we just apply summations and binary shifts, which are
  218. upper bounded by \bigO{\log{n}/2}. Thus, the order of magnitude belongs to
  219. \bigO{\log^2{n}}.
  220. \paragraph{}
  221. Even if both algorithms presented have \emph{asymptotically} the same
  222. complexity, we believe that adopting the one of Dijkstra has lead to a
  223. pragmatic, substantial performance improvement.
  224. \section{RSA Cipher \label{sec:preq:rsa}}
  225. The RSA cryptosystem, invented by Ron Rivest, Adi Shamir, and Len Adleman
  226. ~\cite{rsa}, was first published in August 1977's issue of
  227. \emph{Scientific American}. In its basic version, this \emph{asymmetric} cipher
  228. works as follows:
  229. \begin{itemize}
  230. \item choose a pair $\angular{p, q}$ of \emph{random} \emph{prime} numbers;
  231. let $N$ be the product of the two, $N=pq$, and call it \emph{public modulus};
  232. \item choose a pair $\angular{e, d}$ of \emph{random} numbers, both in
  233. $\integerZ^*_{\varphi(N)}$, such that one is the multiplicative inverse of the
  234. other, $ed \equiv 1 \pmod{\varphi(N)}$ and $\varphi(N)$ is Euler's totient
  235. function;
  236. \end{itemize}
  237. Now, call $\angular{N, e}$ \emph{public key}, and $\angular{N, d}$
  238. \emph{private key}, and let the encryption function $E(m)$ be the $e$-th power of
  239. the message $m$:
  240. \begin{align}
  241. \label{eq:rsa:encrypt}
  242. E(m) = m^e \pmod{N}
  243. \end{align}
  244. while the decryption function $D(c)$ is the $d$-th power of the ciphertext $c$:
  245. \begin{align}
  246. \label{eq:rsa:decrypt}
  247. D(c) = c^d \equiv E(m)^d \equiv m^{ed} \equiv m \pmod{N}
  248. \end{align}
  249. that, due to Fermat's little theorem, is the inverse of $E$.
  250. \paragraph{}
  251. %% less unless <https://www.youtube.com/watch?v=XnbnuY7Kxhc>
  252. From now on, unless otherwise specified, the variable $N=pq$ will always refer
  253. to the public modulus of a generic RSA keypair, with
  254. $p, q$ being the two primes factorizing it, such that $p > q$.
  255. Again, $e, d$ will respectively refer to the public
  256. exponent and the private exponent.
  257. %%% Local Variables:
  258. %%% mode: latex
  259. %%% TeX-master: "question_authority"
  260. %%% End: