HarekazeCTF2019 show_me_your_private_key

harezkazeCTF2019_smypk_solve.go

package main

import (
    "fmt"
    . "./ecUtils"
    . "./mathUtils"
)
// https://github.com/ykm11/goCurve


/*
factor n given (n, e, d)

#E_n(0, b) = #E_p(0, b) * E_q(0, b); n = p*q

cardinality of E_p and E_q are p+1 and q+1 respectively, since p = q = 2 (mod 3) and a=0
#E_n(0, b) = #E_p(0, b) * E_q(0, b) = (p+1) * (q+1)

order = (p+1) * (q+1)
d = inverse(e, order)

C := [e]M
-> [d]C = [ed]M = [1 + k*order]M = M + O = M
/*


/*
[+] (n, e, d) : (9799080661501467884467225188078342742766492539290954649052326288545249523485259554498055327101620585612049935019772095457875188392850174807669467113561703L, 65537, 357800937225887859492043729115941745631326069953205890949878950951199812467762505076908807818483545413271956081271375834809278508559178715879283048960953)
[+] Cx: 4143446088312921816758362264853048120154280049677909632349103364802575463576509561464947871773793787896063253331418475283720886100034333135184249344102365
[+] Cy: 8384037709829308179633895299138296616530497125381624381678499818112417287445046103971322133573513084823937517071462947639275474462359445732327289575301489

[+] (p, q): (105807500383793084625630519283985041680512853206910763583384270571251151476573, 92612344360820268580364307306616213661094478510448287251372441577708991857811)
*/

func main() {
    Cx := Str2Int("4143446088312921816758362264853048120154280049677909632349103364802575463576509561464947871773793787896063253331418475283720886100034333135184249344102365", 10)
    Cy := Str2Int("8384037709829308179633895299138296616530497125381624381678499818112417287445046103971322133573513084823937517071462947639275474462359445732327289575301489", 10)

    p := Str2Int("105807500383793084625630519283985041680512853206910763583384270571251151476573", 10)
    q := Str2Int("92612344360820268580364307306616213661094478510448287251372441577708991857811", 10)
    modulus := Mul(p, q, nil)

    A := Str2Int("0", 10)
    B := Sub(Exp(Cy, TWO, modulus), Exp(Cx, THREE, modulus), modulus) // B = My^2 - Mx^3 = Cy^2 - Cx^3 mod modulus

    order := Mul(Add(p, ONE, nil), Add(q, ONE, nil), nil) // (p+1)*(q+1)
    e := Str2Int("65537", 10)
    d := InvMod(e, order)

    EC := NewCurve(A, B, modulus)
    EC.PrintCurve()

    C := EC.Point(Cx, Cy)
    fmt.Println("[+] C:", Point2Str(C))

    M := EC.Point_xP(d, G)
    fmt.Println("[+] M:", Point2Str(M))
    fmt.Printf("%s%s\n", M.Y.Bytes(), M.X.Bytes())
}

solver_log

[+] EC: y^2 = x^3 + 0x + 9799080661476240009419104842501496507114422480561211954339664262762689292909462164168076052486763023061382180139043303665828664137380077167801234008944274  OVER Zmod(9799080661501467884467225188078342742766492539290954649052326288545249523485259554498055327101620585612049935019772095457875188392850174807669467113561703)
[+] Base Point G: (4143446088312921816758362264853048120154280049677909632349103364802575463576509561464947871773793787896063253331418475283720886100034333135184249344102365, 8384037709829308179633895299138296616530497125381624381678499818112417287445046103971322133573513084823937517071462947639275474462359445732327289575301489; 1)
[+] M: (293287502352283012030139917140690694691558092157, 1614142473028995026146621731223303794610497908; 1)
HarekazeCTF{dynamit3_with_a_las3r_b3am}