math_prequisites.tex 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  1. \chapter{Mathematical prequisites \label{chap:preq}}
  2. \section{Euclid's Greatest Common Divisor}
  3. Being the gratest common divisor a foundamental algebraic operation in the ssl
  4. protocol, \openssl implemented it with the following signature:
  5. \begin{minted}[fontsize=\small]{c}
  6. int BN_gcd(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx);
  7. \end{minted}
  8. The computation proceeds under the well-known Euclidean algorithm, specifically
  9. the binary variant developed by Josef Stein in 1961 \cite{AOCPv2}. This variant
  10. exploits some interesting properties of $gcd(u, v)$:
  11. \begin{itemize}
  12. \setlength{\itemsep}{1pt}
  13. \setlength{\parskip}{0pt}
  14. \setlength{\parsep}{0pt}
  15. \item if $u,\ v$ are even, then $gcd(u, v) = 2gcd(u/2, v/2)$
  16. \item if $u$ is even and $v$ is odd, then $gcd(u, v) = gcd(u/2, v)$
  17. \item $gcd(u, v) = gcd(u-v, v)$, as in the standard Euclid's algorithm
  18. \item the sum of two odd numbers is always even
  19. \end{itemize}
  20. % Donald Knuth, TAOCP, "a binary method", p. 388 VOL 2
  21. Both \cite{AOCPv2} and \cite{MITalg} analyze the running time for the algorithm,
  22. even if \cite{clrs}'s demonstration is fairly simpler and proceeds %elegantly
  23. by induction.
  24. Anyway, both show that algorithm ~\ref{alg:gcd} belongs to the class
  25. \bigO{\log b}.
  26. \begin{algorithm}
  27. \caption{\openssl's GCD \label{alg:gcd}}
  28. \begin{algorithmic}[1]
  29. \State $k \gets 0$
  30. \While{$v \neq 0$}
  31. \If{$u$ is odd}
  32. \If{$v$ is odd}
  33. \State $a \gets (a-b) \ll 1$
  34. \Else
  35. \State $b = b \ll 1$
  36. \EndIf
  37. \If{$a < b$} $a, b \gets b, a$ \EndIf
  38. \Else
  39. \If{$v$ is odd}
  40. \State $a = a \ll 1$
  41. \If{$a < b$} $a, b = b, a$ \EndIf
  42. \Else
  43. \State $k = k+1$
  44. \State $a, b = a \ll 1, b \ll 1$
  45. \EndIf
  46. \EndIf
  47. \EndWhile
  48. \State \Return $a \ll k$
  49. \end{algorithmic}
  50. \end{algorithm}
  51. \section{RSA Cipher}
  52. XXX.
  53. define RSA, provide the simple keypair generation algorithm.
  54. From now on, except otherwise specified, the variable $N=pq$ will refer to the
  55. public modulis of a generis RSA keypair, with $p, q\ .\ p > q$ being the two primes
  56. factorizing it. Again, $e, d$ will respectively refer to the public exponent and
  57. the private exponent.
  58. \section{Algorithmic Complexity Notation}
  59. The notation used to describe asymptotic complexity follows the $O$-notation,
  60. abused under the conventions and limits of MIT's Introduction to Algorithms.
  61. Let \bigO{g} be the asymptotic upper bound of g:
  62. $$
  63. O(g(n)) = \{ f(n) : \exists n_0, c \in \naturalN \mid 0 \leq f(n) \leq cg(n)
  64. \ \forall n > n_0 \}
  65. $$
  66. With the writing $f(n) = O(g(n))$ we will actually interpret
  67. $f(n) \in O(g(n))$.
  68. \section{Square Root \label{sec:preq:sqrt}}
  69. Computing the square root has been another foundamental requirement of the
  70. project, though not satisfied by \openssl. Apprently,
  71. % \openssl is a great pile of crap, as phk states
  72. \openssl does not provide
  73. XXX.
  74. define square root in the algebraic notation
  75. discuss method of computation for square root
  76. %%% Local Variables:
  77. %%% mode: latex
  78. %%% TeX-master: "question_authority"
  79. %%% End: