Challenge


Solve:

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES 
import heapq

with open("SPARSERSA.crt", "rb") as f:
    key = RSA.import_key(f.read())

n = key.n
e = key.e

#https://github.com/google/google-ctf/blob/master/2020/quals/crypto-yafm/solve.py
def CheckLowHammingWeight(n, cutoff = 2500, maxsteps = 10**6):
  """Tries to factor n assuming that the factors have a low Hamming weight.


  This algorithm is loosly based on crackpot claims that the bit
  patterns for the prime factors can be derived from the bit pattern
  of the product. This doesn't work for general integers, but may
  work if n is the product of two factors with a small Hamming weight.

  Args:
      n: the modulus to test
      cutoff: the number or steps after which the search is abandoned if
           no promissing branch has been found. The default of 2500 means that
           the function takes about 100 ms when n is not a product of factors
           with a low Hamming weight.
      maxsteps: an upper bound on the maximal number of steps. The default
           value 10**6 means that the search spends about 20 seconds before
           giving up. A value of 10**7 is the largest value tested with
           64 GB of memory.
  Returns:
      A tuple (weak, factors), where the value weak is True if the modulus
      is (probably) weak, and a list of factors that were found.
      The test can fail even if no factors were found. This happens when
      the search finds a partial factorization with unusually low
      Hamming weight. E.g., the following cases can be detected without
      finding a factorization:
         * the Hamming weight of the factors is close to the bound that
           can be factored. E.g. products of two 1024-bit primes with
           Hamming weight 96 often require 10**7 or more steps to factor.
         * only the most significant bits of the factors have a small
           Hamming weight. The key may still be weak because other methods
           such as Coppersmith may be used to find the least significant bits.
         * the primes are not of equal size. The search will still find
           partial factorizations with low Hamming weight, but fail to factor n.
         * the search spends a lot of time with false positives. The product
           of two factors of very low Hamming weight often has other partial
           factorizations with low Hamming weight.
  """

  def Heuristic(hamming_weight, rem_size):
    """The heuristic used for the search.

    The heuristc (in particular the factor 5) has been determined
    experimentally. Using a factor 5 in this heuristic allows to factor
    some 2048 bit products where each of the 1024-bit factors has a Hamming
    weight 96. The factor 5 has the property that the heuristic of correct
    guesses are expected to slowly decrease with more bits of the factors
    guessed, while the heuristic of incorrect guesses are slowly increasing.

    Args:
      hamming_weight: the Hamming weight of the partial factors p0 and q0
      rem_size: (n - (p0 << bit) * (q0 << bit)).bit_length()

    Returns:
      the heuristic. Smaller is better.
    """
    return rem_size + 5 * hamming_weight

  # A heap containing partial factorizations.
  # This heap is being used by the function Push below.
  # Elements in the heap are quintuples (v, hw, bit, p0, q0) where:
  #   v: is the result of the function Heuristic above.
  #   hw: is the sum of the Hamming weights of p0 and q0.
  #   bit: is the number of missing bits in p0 and q0.
  #   p0: a guess for the msbs of p, i.e., the value p >> bit.
  #   q0: a guess for the msbs of q, i.e., the value q >> bit.
  heap = []

  def Push(p0, q0, hw, bit, rem_size):
    """Computes the heuristic and pushes the values into the priority queue.

    Args:
      p0: a partial factor.
      q0: a partial factor.
      hw: the sum of the Hamming weights of p0 and q0
      bit: the number of bits that are still to guess.
      rem_size: (n - (p << bit) * (q << bit)).bit_length()
    """
    # invariants:
    # assert (p0 << bit) * (q0 << bit) <= n < ((p0+1) << bit) * ((q0+1) << bit)

    # The algorithm looks for a factorization where p <= q.
    if p0 <= q0:
      v = rem_size + 5 * hw
      heapq.heappush(heap, (v, hw, bit, p0, q0))

  # There are two thresholds for the heurisitic.
  # If no value of the heuristic smaller than threshold_cutoff is found then
  # the search is stopped after cutoff steps. Hence checking a correctly
  # generated RSA key will very likely stop after cutoff steps.
  # If a small value or the heuristic is found then search will continue until
  # a factorization is found or maxsteps steps were made. If at this point
  # the minimal value for the heuristic is smaller or equal to threshold_weak
  # (and no factorzation was found) then the RSA key is considered to be
  # potentially weak. Such keys may need to be analyzed further.
  threshold_cutoff = n.bit_length()
  threshold_weak = n.bit_length() - 12

  psize = (n.bit_length() + 1) // 2
  steps = 0
  remainder = n - (1 << (2 * (psize - 1)))
  Push(1, 1, 2, psize - 1, remainder.bit_length())
  # smallest value for the heuristic
  minv = Heuristic(2, remainder.bit_length())
  while steps < maxsteps and heap:
    steps += 1
    if steps == cutoff:
      if minv >= threshold_cutoff:
        break

    v, hw, bit, p, q = heapq.heappop(heap)
    if v < minv:
      minv = v
    # Doing computations on the msbs only saves 40% CPU time.
    while bit >= 1:
      p <<= 1
      q <<= 1
      bit -= 1
      n0 = n >> (2 * bit)
      for dp, dq in ((0, 1), (1, 0), (1, 1)):
        # min = pq + p, pq + q, pq + p + q + 1
        p0 = p + dp
        q0 = q + dq
        # The algorithm guesses at this point that the factors of n are
        # in the range [p0 << bit, (p0 + 1) << bit]
        # and the range [p1 << bit, (p1 + 1) << bit].
        rem0 = n0 - p0 * q0
        if rem0 < 0:
          break
        if bit:
          if rem0 <= p0 + q0:
            rem_size = rem0.bit_length() + 2 * bit
            Push(p0, q0, hw + dp + dq, bit, rem_size)
        else:
          if rem0 == 0:
            return True, [p0, q0]
      else:
        if rem0 > 0:
          break
  potentially_weak = minv <= threshold_weak
  return potentially_weak, []

res, factors = CheckLowHammingWeight(n)
if res and factors:
    p, q = factors
    assert p * q == n
    print(f"{p = }")
    print(f"{q = }")

 
# openssl smime -in flag.encrypted -pk7out -out flag.pk7
# openssl pkcs7 -in flag.pk7 -print
enc_key = 0x5f529c47a63e1447f95ce19263e59a2696dd661030bf2218bcea8a1cff4dc75328aab000db9ceca904b831ff7388ef3b3c97cb72dedbc0afecfa0d48403403f0c61591b08b36da8fb30653d126077e86f16f35f5e372b557a046bbc4b6f8cba7a4bcd1ed21d6071d9d42d377f50c80a79c3a757596455d29bce5188d7139a53d
enc_data = '58a36ff32aab152227245bcf96b4cd0128c8be8fb13f8c07abafa124c17b444d904a8ba4a978667e48bc0bb3bee9fe9b'
iv = '2e89748834a486de139c6bc25e604c79'

d = pow(e, -1, (p-1)*(q-1))
key = bytes.fromhex(hex(pow(enc_key, d, n))[-64:])
enc_data = bytes.fromhex(enc_data)
iv = bytes.fromhex(iv)

cipher = AES.new(key, AES.MODE_CBC, iv)  
print(cipher.decrypt(enc_data))
# so{8175d69b57c9fac9e9223a9829b19beb}