welcome to rsa.rb

require 'prime'

# calc (x,y) s.t. ax + by = gcd(a,b)
def extgcd(a,b)
  g = a
  x = 1
  y = 0
  if b != 0
    o = extgcd(b, a%b)
    x = o[:y]
    y = o[:x]
    g = o[:g]
    y -= (a / b) * x;
  end
  return {g:g, x:x, y:y}
end

# calc a^b mod m
def modpow(a,b,m)
  r = 1
  while b>0
    r = r*a%m if (b&1)==1
    a = a*a%m
    b >>= 1
  end
  return r
end

# calc a^-1 mod m
def modinv(a,m)
  ret = extgcd(a,m)[:x]
  return ret<0 ? ret+m : ret
end

# check it is prime
# from : https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95#.E3.82.B3.E3.83.BC.E3.83.89.E4.BE.8B
def prime?(n)
  return true if n == 2
  return false if n == 1 || n & 1 == 0
  d = n-1
  d >>= 1 while d & 1 == 0
  20.times do
    a = rand(n-2) + 1
    t = d
    y = modpow(a,t,n)
    while t != n-1 && y != 1 && y != n-1
      y = (y * y) % n
      t <<= 1
    end
    return false if y != n-1 && t & 1 == 0
  end
  return true
end

# random prime
def randprime(min, max)
  while true
    ret = rand(max-min) + min
    if prime?(ret)
      return ret
    end
  end
end

# euler's phi function
def phi(pp,qq)
  if pp == qq
    return pp * (pp-1)
  else
    return (pp-1) * (qq-1)
  end
end

# here is flag!
mes0 = "***CENSORED***"
mes0 = mes0.unpack("H*")[0].to_i(16)
# private key
p0 = 0x141e3aa4f32f59c29ccc6f80946b50e51
q0 = -1 # CENSORED
# public key
n0 = 0x24eb33d74405613381a6583310af3a8bde7cb9bb2b2bf56cb4dd979de737d6e83
e0 = 65537
# encrypt
cip0 = modpow(mes0, e0, n0)
# cip0 = 0x7a799e0b6f6e009851c74ea3a97ec79a449a92d4954004f77fc4165b43b9bfa5
puts cip0.to_s(16)
# decrypt test
puts [modpow(cip0, modinv(e0,phi(p0,q0)), n0).to_s(16)].pack("H*")