```html                         SECT-CTF 2018 write-up                                Matsign
Abstract
   This is a write-up for the Matsign challenge of SEC-T CTF 2018 by   LarsH on behalf of team Hacking for Soju.
Table of Contents
   1.  Description   2.  Figuring out the behaviour   3.  Solution   4.  Overkill solution
1.  Description
   The challenge was running on 178.128.171.133:5555, and the flag was   said to be the lowest 20 digits of d.
   When connecting to the service, it presents this interface:
                                               __                                              /C/             MatSign Cryptographic Service   /I/             -----------------------------  /B/                                           |/                 Security in            | a b c |                 multiple               | d e f |                 dimensions             | g h i |
       Give comma-separated matrix to sign:
   Trying some bogus data gives the error message: "Something went   wrong... size needs to be 3x3" and the service disconnects.
2.  Figuring out the behaviour
   If we give the service nine comma separated digits, the service   replies with a 2x3 matrix with quite large numbers.
   If we supply the identity matrix 1,0,0,0,1,0,0,0,1 the reply from the   service is
   [[1L, 0L, 0L], [0L, 1L, 0L]]
   And with the hint that the flag has to do with d, this is probably an   RSA signing procedure using matrices, with a reply that is truncated   to only the two first rows of the signed matrix.
   To test this hypothesis, we signed 2,4,3 and 9 using only the upper   left matrix element.  This gave us
2**d % n = 60367950465822685225873385712767653643824839855352646450606550016478920892468788806193056971340519189632591200228322574450863215073463938809513217771274542181517095033089064858707397983692859025528030266901235936177543512852674831795529276636510222747378681491655760328983542122308539965569062960418027228183L
4**d % n = 92687565588710900782013885164183849434282071464202225627698001088281369083202978850909071939396731888865937257211783503498517481458171092865273336295026797869703015863915090194525002754182145189889112596727319217539029163128430230826432702708375423212724719649924819226542225995482529552443813838549471313322L
3**d % n =100278301404568098916200236917488272751939485100468225051662323295197931456945237050522241170678807530733514341047234698367738018287290685132701072323828854269947954282966894224501004830602997484035859849328863700700985004106527522352685174235357463416363798084052572369869218241585397948175808995950214249823L
9**d % n = 49596771524844018332117907446667714330366839281956416218193856672993584684880325084294326181161165473234176322716648852264854729112396270122126314023394292494514798092233165344163700661542242635437487249637139838727143843595536500038124674914252524999992711503900926307291857797248003824799689533766593838147L
   And we can now compute the value of n.  Because
 (2**d % n)**2 = (4**d%n) + a*n    and    (3**d % n)**2 = (9**d%n) + b*n
   then
    n = c * GCD( (2**d % n)**2 - (4**d%n) , (3**d % n)**2 - (9**d%n) )
   There might be some extra factor c, but in this case c was 1.
n = 116788087953963032128385585709862438579640318389622830261185262874480819325358293077704265052032681793494472152951802121882380333334023139095912125054377042735842604051268793107461339994293857847113821983101449621970807824673056692848762006415090468821976791496266369267044931986102543085443093592771899364043L
   We finally verify the hypothesis with the commonly used public   exponent e = 0x10001
>>> pow( 60367950465822685225873385712767653643824839855352646450606550016478920892468788806193056971340519189632591200228322574450863215073463938809513217771274542181517095033089064858707397983692859025528030266901235936177543512852674831795529276636510222747378681491655760328983542122308539965569062960418027228183L, 0x10001, n)2L
   so the signed value of two is indeed two when verified with the   public exponent.
3.  Solution
   After some thought, we found out that this uppertriangular matrix can   be used to leak out d:
      | 1 1 0 |**d   | 1 d 0 |      | 0 1 0 |    = | 0 1 0 |      | 0 0 0 |      | 0 0 0 |
   This is because exponentiation is just repeated matrix   multiplication; every multiplication with this matrix to itself will   increase the top middle element by one:
      | 1 1 0 |   | 1 i 0 |   | 1 (i+1) 0 |      | 0 1 0 | * | 0 1 0 | = | 0   1   0 |      | 0 0 0 |   | 0 0 0 |   | 0   0   0 |
   So the solution that leaks out d is
$ echo 1,1,0,0,1,0,0,0,0 | nc 178.128.171.133 5555
                                        __                                       /C/      MatSign Cryptographic Service   /I/      -----------------------------  /B/                                    |/          Security in            | a b c |          multiple               | d e f |          dimensions             | g h i |
Give comma-separated matrix to sign: [[1L, 5943028721584245726050413176410138283154560962958208934205911953345339769139110844471729312427010601359599380961811802134332337636281294061139004486875312629626670328759705858180306009474028254361071673572477363571820379071571307323768821649021601211516734751578279378417106050597533639902738566133769973073L, 0L], [0L, 1L, 0L]]
   The value 59...73L is of d, and the flag is the last 20 digits of   this number.
   >>> 'SECT{%u}'% (d % 10**20)   'SECT{2738566133769973073}'
4.  Overkill solution
   As we now have both n, e and d, it is possible to fully factorize n   into p and q.  This is because of the relation
   e*d = 1 (mod phi(n))   e*d = 1 + K*(p-1)(q-1) = 1 + K(p*q-p-q+1) = 1 + K(n-p-q+1)  (eq.A)
   and as n is very large compared to p, q and 1, we can compute K as
   K = round(e*d/n) = (e*d + n/2) // n = 3335
   and we can now rewrite (eq.A) to express the sum of p and q and fully   factorize n
   p+q = 1 + n - (e*d-1)/K   q = 1 + n - p - (e*d-1)/K   n = p*q = p * ( 1 + n - p - (e*d-1)/K )   0 = p**2 - p(n+1 - (e*d-1)/K) + n
   A = (n + 1 - (e*d-1)/k) / 2   p = A + sqrt(A**2 - n)
   The factors p and q are
p = 13366307433997958707964470222520173887015112672699734346723683511568607076923294855549140374608334350841149318231659041457171104749357709779496554220581913q = 8737498260507305634520033781659157635088054656248608647433097973262598642807611526467945801713981127525934898453762929448056973637158526184438433905851011```