math_prequisites.tex 12 KB

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