Little e.md

BCACTF 2.0 – Little e

• Category: Crypto
• Points: 100
• Author: Vivian

Challenge

Gerald's favorite prime is 3 and made it his public exponent; he keeps insisting that it's secure. Help me prove him wrong.

Solution

We're given:

N: 17260541145579198891286838820507756585494408484294770862002805660577661138753926064444981930310528890773266098356882517290033235056654103412024620204547445159627671127518965960486480229617902782023368077819854820837387791591683428592246121552228695417314295153721144499366280389254552597040315734269703314601367296670296596449184388246232676724558126845148454433428619114310396032130452938580427564701080866025573039407415733982384144637567337164211240182263026767455207192185903776322079215198832973810587735067694801737731617941390472537291532113711292822595269219795255224521641891049508289784761579371125213474439
e: 3
ct: 1112413624683819960899152482895461211039349964898672381675850025556800617245120168928400758297834676330400246617472191750627367991315450127361583383350639760738254818244740474313061192563860605923503717

When e is tiny, the plaintext can be found by taking the e^th root of ct Some code on Stack Overflow can help us with this:

def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

c = 1112413624683819960899152482895461211039349964898672381675850025556800617245120168928400758297834676330400246617472191750627367991315450127361583383350639760738254818244740474313061192563860605923503717
e = 3
print(hex(find_invpow(c, e)))

This gives us "0x6263616374667b5235345f4e30545f35305f5333435552335f33337dL" which we can then stick in a hex editor: