For Wednesday October 4th, 2023

  1. I wish to factor $n=38191$.  How do I do it, if I have the following info: 
    196 ^2 - n factors as 3^2 * 5^2
201 ^2 - n factors as 2 * 5 * 13 * 17
214 ^2 - n factors as 3^2 * 5 * 13^2
227 ^2 - n factors as 2 * 3^3 * 13 * 19
229 ^2 - n factors as 2 * 3 * 5^3 * 19
241 ^2 - n factors as 2 * 3^2 * 5 * 13 * 17
254 ^2 - n factors as 3^4 * 5^2 * 13
  2. Look at the Quadratic Sieve Tools page.  Do these things to get familiar with it:
    1. Initialize the first box, see how it gives you n and k.
    2. Change n, see how k changes.
    3. Run the second box to get a factor base.
    4. Make your factor base bigger.
    5. Run the third box to factor things in the list k^2-n, reporting only those that factor in the factor base.
    6. Change m in the third box to get more relations.
  3. Factor $n=31861$ using the Quadratic Sieve Tools page to produce the relations you will need.   You may need to expand your factor base or the number of relations the boxes produce.
  4. If you got lucky and got a single relation that did it, can you instead find a pair or larger combination of relations that do it?
  5. Suppose Eve listens in to an RSA session, so she knows Bob’s public key $(n,e)$ and the ciphertext $c$.  Suppose she computes two lists:  (a) a list of $c x^{-e} \pmod n$ for many small $x$; (b) a list of $y^e \pmod n$ for many small $y$.
      1. Explain how she can compute the message if she finds a collision between these two lists.
      2. How likely is a collision?  What would have to be true about the message for a collision to happen?