Solution: "Three can keep a secret"

Bob sends the same ASCII message to each of his three friends, Alice, Carol, and Dave.

Alice's public key is:
n1 = 25126171490550949137067166545080770462245072243858392176349217979422494742080344557208919718601413707067740432352916395109196231236534566389985061669696131059355698716228798660767968230495858798622575184510397257466120112009968603434060166083769072316754138621023912998346182046544458255193764947595408483470561246531247399247616083919742692616913116789602346331401727917193148690808960388988899038719646697227508145902541775249921541015370584407323514316373060632674988498832825815928878119941819360073204560607616497410708714250992508897099668175615842550883662601337507793186164528630279272798292570345329490474657
e1 = 3

and she receives:
c1 = 22644160532424166647302481908331843211558990111140457245518433182006437451920964646983959188140919292137642257720294335384750417131543443838625731350426584617500036686022734911316984348919920609324804645844992492208613624228797022977951911331559349250193084670468461173511665944029084459057833490496965929762995738426696112282385296216296505892428670034822981250390285023732505173347270328742139533411515868247305679051257626043481286886099104675689010967684215368798104829050322553203100367114365372986583092417552139513243408181942980157221673676286302728281659516189156455307152947342985643701575435968684842519390

Carol's public key is:
n2 = 27260308252980389500291814286027323747043619408543944715114490363838117423060176644721500885697593887763937157789653918806396377392642237065238533700772388673650175360707149117753489325200620365693887800671251538346455137405446831771883729742296962469053854703399672546790924309240754309822887462171960958959351381197115208741369991046157072414070376319412921721772573626556076212531213356756797502857319549172958466078346696282529239749483520454377558909530264717140981455101749971183568492332053430412714946196370474629683053908459708879335819807655377297960198005509175897756107739419780198478796528608220187589881
e2 = 3

and she receives:
c2 = 11693212775658550720371089343405430474369571209548850835206671076378377273388230179722938433759726890490683481034729331281065402685015045077617932057038548764015292446866695309323894050702152023594818173459631681652267737741779958948641830523464036050487902623969207364333788110946733424677262849725037932777432033025519208275379004837050272376275721730277024677261013955240869203439030039352353892829812403671145451846964242855046225645968271517034976352420822340551083666325574252116319196163945204331177018374511017886390288081281981469807911329984030283355401616469671121567940098696675773668613262514060147953997

Dave's public key is:
n3 = 23386630043694450983096068094193088348046299522414235292640580732763847017592549344548967349831638250185948775568475805191121167602996518494691427339958114934188252858318358225205022419794227267276374738145740003800799670875511272894725535776885361747614890316969782570523675456587601445678111026960224225757348118313769870564468728566932721547635428193204705102528337649097090587298290430519417574718405024334222268760073092051392700778335369922566330912113763974555633296042952477941880090806494890075693945358451320293634044625844371447618138349679180606125038750503801383424811925288269362856028465810197588739227
e3 = 3

and he receives:
c3 = 10570107871312491667989075163037727253083085589392430403843918970557457916514207491253534217736104196970484388675371140202752399117851882496523920717833091446146529508661136709772483229249271900553786479956282028463825605913112938820175565126851090282287149507626842785122242494967462753361782595749374169965892719189251311008901040866408222623467219820559547517067606290948321792443508068546730869925997656922153622467107100538836646865543117608962434135860046403255072847914393951884078125519829030103909837197964666111110000436029781933878200727387204422132638541043002315222341029027418636355780540695851687217311

"Three may keep a secret, if two of them are dead."
  -- Benjamin Franklin, Poor Richard's Almanack

If the same message m is encrypted with e different public keys, then the original message can be recovered without the private key. This is Håstad's broadcast attack. It's most useful when e is 3, since only 3 messages are needed. This attack applies primarily to textbook RSA where there is no padding; modern padding schemes mitigate it.

The RSA decryption function is c = m^e (mod n), so suppose that e=3 and M = m^3. We must now solve this system of equations:

M ≡ c1 (mod n1)
M ≡ c2 (mod n2)
M ≡ c3 (mod n3)

Assuming all three ns are coprime, the Chinese Remainder Theorem indicates that there is a solution for the system exists. To find this solution, first find:

N = n1*n2*n3
N1 = N / n1
N2 = N / n2
N3 = N / n3

gcd(Ni, ni) = 1 for each pair Ni and ni, so the modular multiplicative inverse ui must exist such that Ni * ui = 1 (mod ni). Find each inverse u1, u2, and u3. Therefore:

M ≡ c1*N1*u1 + c2*N2*u2 + c3*N3*u3 (mod N)

Since m < n for each message, m^3 < n1*n2*n3 and M = m^3. Find the cube root of M to recover the original message.

Python 3.8+ code

# find_invpow adapted from https://stackoverflow.com/q/55436001
# by user GMX Rider (https://stackoverflow.com/users/8207239/gmx-rider)
# CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/legalcode)
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

n1 = [as above]
c1 = [as above]
n2 = [as above]
c2 = [as above]
n3 = [as above]
c3 = [as above]

e = 3

N = n1 * n2 * n3
N1 = N // n1
N2 = N // n2
N3 = N // n3

u1 = pow(N1, -1, n1)
u2 = pow(N2, -1, n2)
u3 = pow(N3, -1, n3)

M = (c1*N1*u1 + c2*N2*u2 + c3*N3*u3) % N
m = find_invpow(M, 3)

Applied to the challenge

Using the above code, we find m to be:

m = 186576314465159171206572697173754806981509321675655648776614523032773455457361390801192678189859864088187148169981814221757456882655522670736473272289076707789729388576613685689382980630853081842314743476285631463193232725295173581041890295056874188827094127

Converting this integer to hexadecimal and then to ASCII, we get:

charlie oscar papa papa echo romeo sierra mike india tango hotel underscore zulu Juliet mike five golf kilo

The flag:

coppersmith_zJm5gk

Online tools:

My own RSA calculator