그래도 후기를 쓰기는 해야 할 것 같아서 ㅋㅋㅋㅋㅋ 아쉽지만 작년에 비해서 좋은 결과가 나오지는 못했다. 이유는

  • 작년처럼 팀연습을 10번 이상 열심히 굴리지를 않았음 (올해 팀연습 0회)
  • 팀들이 작년보다 전반적으로 강해지고 센 팀들도 더 등장함
  • 일단 내가 작년에 비해서 간절함이 없었음 (애초에 작년에 뽑은 성과가 너무 좋았음) 

그래서 솔직히 결과에 아쉬움이 있어도 "이거 이상을 바라면 그건 그거대로 양심 X"라고 생각하고 있다.

아쉽다고 쳐도 9등이면 동상이고 이정도면 꽤 깔끔한 CP 대회 마무리 아닐까 싶기도 하고 ^__^ 

  • 열었더니 B가 쉬워서 빠르게 풀었음
  • A가 풀이 자체는 쉽다는 콜이 나옴. C 문제 해석에서 약간의 뇌절
  • E가 풀만하다는 콜과 G도 쉽다는 콜이 나옴. G에서 함정 빠짐
  • E 맞추고 G는 계속 맞왜틀. J 풀이 나옴. H가 simple FFT인거 보고 바로 구현, AC
  • C도 풀이 나오고 L 준비 시작. J 짜서 AC. G 다른 풀이도 짜봤는데 또 틀림.
  • G 함정 발견 및 C 구현 후 C, G 모두 AC. L은 DnC 콜이 나왔는데 틀리는 중.
  • L DM 돌리면서 틀린 이유 발견. Money For Nothing 생각하면서 풀이 고쳐서 맞음
  • 이제 junie가 A 구현하면서 다른 풀 거 찾아 떠남. I 보는게 맞는 판단인데 F가 할만해보여서 (ㅋㅋ) 시작
  • F 문제 잘못 이해해서 SCC 문제인줄 알았음 ㅋㅋ
  • junie가 A를 개고통받으면서 결국 AC 성공. 8솔해서 대충 이정도면 그래도 나쁘지 않다고 생각했음
  • F 예제 만들어보다가 결국 문제 이해를 못해먹겠다는 결론을 얻고 그대로 사망

이제 내년부터 ICPC 판 재밌어질텐데 팝콘각이나 열심히 재야겟다 ^____^

저작자표시 (새창열림)

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 2차 예선 풀이  (1) 2021.08.07
SCPC 2021 1차 예선 풀이  (0) 2021.07.16
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05




2등상을 받았다. 실제 실력에 비해 너무 높은 상이다.


UPD: 상금과 트로피까지 전달 받았다. 이제 수상 소감이 올라오면 끝인데 얼굴 팔릴 생각에 걱정이다 ㅜㅜ

UPD: 수상 소감까지 올라왔습니다. 얼굴도 팔렸네요 ㅋㅋ;


대회 과정

  • 1번 열었더니 쉬워서 빠르게 풀었다. 새로고침하니 퍼솔 같아서 기분이 좋았음 ^~^
  • 2번 열고 일단 SCC를 짤 줄 알면 $\mathcal{O}(m^2)$이 뚝딱임을 파악했다
  • 그런데 뇌절해서 그 풀이가 $\mathcal{O}(nm)$인 것으로 착각을 했다.
  • 아무튼 $\mathcal{O}(m^2)$ 풀이를 짜서 긁으려고 했는데 틀리더라. 멘붕 옴
  • 나중에 내 풀이가 $\mathcal{O}(nm)$이 아님을 깨달았다. 그래서 목표를 $\mathcal{O}(nm)$ 풀이 찾는 거로 잡았다.
  • 그러다가 문제에 오류가 있다는 공지를 받고, $\mathcal{O}(nm)$ 풀이 찾기에 착수했다.
  • 풀이 자체는 빠르게 나왔는데, 2번 문제치고 너무 복잡해서 뇌절이었나 걱정했다.
  • 그런데 2번 데이터가 수정된 이후에도 만점자가 4명 뿐이더라. 시간이 꽤 지난 것 치고 적은 수였다.
  • 그래서 맞는 풀이라는 확신을 할 수 있었고. 빠르게 짜서 바로 AC. 5번째 솔브로 기억한다. 이때가 1시간 정도 지났을 때.
  • 3번을 열었는데 일단 문자열에다가 드럽게 복잡한 것 같아서 일단 걸렀다. 전날에 연습을 좀 했는데 힘겨워서 ㅋㅋ
  • 그래도 3번은 풀어야 한다고 생각을 했고, 그 전에 4, 5번에서 빠르게 긁을 수 있는 것을 긁어오는 게 좋다고 판단했다.
  • 4번을 열었는데, 일단 마음 속으로 $\mathcal{O}(n^3 \log n \log MAX)$ 쯤 되는 풀이가 나왔다. 4-2까지 긁힐 것으로 예상했다.
  • 짜는 것도 별로 어렵지 않아서 빠르게 짰는데, 예제 1이 안나오네? 사실 상당히 큰 가정을 기반으로 한 풀이였다.
  • 예제가 안 나온다는 것은 가정이 틀렸다는 거고, 결국 간단하게 고치는 것 자체가 쉽지 않다는 것이다. 똑떨...
  • 5번을 열었더니 뭔 이상한 트리가 튀어나와서 바로 걸렀다. 결국 소득 없이 3번으로 돌아왔다.
  • 3번의 풀이 자체는 스트링 티피컬 짬뽕 국밥 든든 그 자체여서 빠르게 찾을 수 있었다. 문자열 관련 대비도 꽤 했고.
  • 그런데 아무리 생각해도 코드가 300줄 뽑히게 생겨서 마음을 굳게 먹어야 했다. 다행히 이때도 2번 만점자 수가 20명인가 그랬다.
  • 3번을 풀면 매우 큰 상을 받을 가능성이 높다고 생각해서, 뇌절하지 말자고 생각하고 짜기 시작했다
  • 대충 한 파트 짜고 -> 스코어보드 확인하면서 안도하고 -> 한 파트 짜고 -> 안도하고를 반복
  • 다 짰더니 에러가 조금 났는데, 인덱스 실수 하나여서 금방 고쳤다. 예제 나와서 제출했더니 한 방에 맞더라 ㅋㅋ
  • 이때가 4시 15분. (3시간 15분 지났을 때) 이제 긁을 것을 찾아서 떠났고 5-1이 긁기 쉽다는 결론을 얻었다.
  • 사실 긁기 별로 안 어려운데, 뇌가 극도의 흥분상태여서 뇌절도 꽤 해서 40분 정도 걸렸다. 이때가 5시.
  • 4번을 긁으면 진짜 2등상에 못 박는 느낌이어서 무리를 좀 했다. 뚫으려고 별 짓을 다하다가 사망하고 패배를 인정했다. 


문제 풀이


1. 더도 말고 덜도 말고


매우 쉬운 문제. 백준에도 비슷한 문제가 많을 것으로 생각한다. std::map 사용하면 뚝딱.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
 
ll n, k, ans;
map<ll, ll> M;
 
void solve(void)
{
    ans=0; ll i, tot=0, x; cin>>n>>k;
    M.clear(); M[0]++;
    for(i=1 ; i<=n ; i++)
    {
        cin>>x; tot+=x;
        ans+=M[tot-k];
        M[tot]++;
    }
    cout<<ans<<"\n";
}
 
int main(void)
{
    fio; int i, tc;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


2. 영원한 휴가


작년 2번에 비해서 상당히 난이도가 올라간 문제. solved.ac 기준 플레 1 ~ 다이아 5 정도라고 개인적으로 생각한다.

$\mathcal{O}(m^2)$ 풀이는 간단한데, 그냥 SCC를 모든 경우에 대해서 다 구해주면 된다. 이러면 섭테 2까지 긁힌다.

본 문제를 해결하려면 SCC를 압축하여 DAG를 만드는 과정을 생각할 필요가 있다. 이제 기존 간선 $u \rightarrow v$를 뒤집었다고 생각하자.

  • $u, v$가 같은 SCC에 포함되었다면, 그 간선을 뒤집어서 SCC 크기가 증가하지는 않을 것이다. 그러니 무시해도 된다.
  • $u, v$가 다른 SCC에 포함되었다면, DAG 상에서 $u$의 SCC에서 $v$의 SCC로 가는 간선이 있다는 것이다.
  • 만약 이 간선을 뒤집는다면, 어떻게 될까? 만약 해당 간선이 $u$의 SCC에서 $v$의 SCC로 가는 유일한 경로라면, 무시해도 된다.
  • 하지만 $u$의 SCC에서 $v$의 SCC로 가는 경로가 2개 이상이라면, $u$의 SCC와 $v$의 SCC "사이"에 있는 모든 SCC가 묶인다.
  • 여기서 "사이"에 있다는 것은, $u$의 SCC -> ??? -> $v$의 SCC 형태의 경로가 존재하는 ??? 들을 의미한다.

이제 문제를 해결할 수 있다. SCC 압축 DAG를 만든 후, $dp[u][v]$를 $u$번 SCC에서 $v$번 SCC로 가는 경로의 개수가 0개인지, 1개인지, 아니면 2개 이상인지로 정의하자. 이 값은 DAG에서 위상정렬 DP를 하듯이 계산할 수 있으며, 시간복잡도는 $\mathcal{O}(nm)$이다. 이 값을 잘 계산해놓으면 위 관찰을 통해서 답을 얻는 것 역시 쉽게 할 수 있다. 구현을 효율적으로 해야 AC를 얻는다는 말이 있으니, 잘 구현해야한다. $dp$ 계산에서 오버플로우에 주의하자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
 
int n, m, cnt, gr, org;
int ord[1111];
vector<int> cedge[1111];
vector<int> redge[1111];
int vis[1111], whi[1111], sz[1111];
pair<int, int> E[11111];
int forw[1111][1111];
int cntw[1111][1111];
int indeg[1111];
queue<int> Q;
 
void dfs1(int v)
{
    vis[v]=1;
    for(int i=0 ; i<cedge[v].size() ; i++)
        if(!vis[cedge[v][i]]) dfs1(cedge[v][i]);
    ord[++cnt]=v;
}
 
void dfs2(int v)
{
    vis[v]=1; whi[v]=gr; sz[gr]++;
    for(int i=0 ; i<redge[v].size() ; i++)
        if(!vis[redge[v][i]]) dfs2(redge[v][i]);
}
 
int calc(void)
{
    int u, v, i, j, ret=0; gr=0; cnt=0;
    // can be optimized
    for(i=1 ; i<=n ; i++) ord[i]=0;
    for(i=1 ; i<=n ; i++) cedge[i].clear();
    for(i=1 ; i<=n ; i++) redge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        u=E[i].first; v=E[i].second;
        cedge[u].push_back(v);
        redge[v].push_back(u);
    }
    memset(whi, 0, sizeof(whi));
    memset(sz, 0, sizeof(sz));
    memset(vis, 0, sizeof(vis));
    for(i=1 ; i<=n ; i++)
        if(!vis[i]) dfs1(i);
    reverse(ord+1, ord+n+1);
    memset(vis, 0, sizeof(vis));
    for(i=1 ; i<=n ; i++)
    {
        v=ord[i];
        if(!vis[v])
        {
            gr++; dfs2(v);
            ret=max(ret, sz[gr]);
        }
    }
    return ret;
}
 
void solve(void)
{
    int i, j, u, v; ll ans=0; cin>>n>>m;
    for(i=1 ; i<=m ; i++)
        cin>>E[i].first>>E[i].second;
    org=calc();
   // for(i=1 ; i<=n ; i++) cout<<whi[i]<<" "; cout<<"\n";
   // for(i=1 ; i<=gr ; i++) cout<<sz[i]<<" "; cout<<"\n";
    memset(indeg, 0, sizeof(indeg));
    for(i=1 ; i<=gr ; i++)
        for(j=1 ; j<=gr ; j++) cntw[i][j]=0, forw[i][j]=0;
    for(i=1 ; i<=n ; i++) cedge[i].clear();
    for(i=1 ; i<=n ; i++) redge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        u=E[i].first; v=E[i].second;
        if(whi[u]!=whi[v])
        {
            cntw[whi[u]][whi[v]]++;
            cedge[whi[u]].push_back(whi[v]);
            indeg[whi[v]]++;
        }
    }
    while(!Q.empty()) Q.pop();
    for(i=1 ; i<=gr ; i++) forw[i][i]=1;
    for(i=1 ; i<=gr ; i++) if(!indeg[i]) { Q.push(i); forw[i][i]=1; }
    while(!Q.empty())
    {
        int v=Q.front(); Q.pop();
        for(i=0 ; i<cedge[v].size() ; i++)
        {
            int nxt=cedge[v][i];
            int cntv=cntw[v][nxt];
            for(j=1 ; j<=gr ; j++)
            {
                if(forw[j][v]==0) continue;
                if(forw[j][v]==1 && cntv==1) forw[j][nxt]++;
                if(forw[j][v]>=2 || cntv>=2) forw[j][nxt]+=2;
            }
            indeg[nxt]--; if(indeg[nxt]==0) { forw[nxt][nxt]=1; Q.push(nxt); }
        }
    }
    for(i=1 ; i<=m ; i++)
    {
        u=E[i].first; v=E[i].second;
        if(whi[u]!=whi[v] && forw[whi[u]][whi[v]]>=2)
        {
            int tot=0;
            for(j=1 ; j<=gr ; j++)
            {
                if(forw[whi[u]][j]>=1 && forw[j][whi[v]]>=1)
                    tot+=sz[j];
            }
            if(tot>org) ans+=tot;
        }
    }
    cout<<ans<<"\n";
    for(i=1 ; i<=n ; i++) cedge[i].clear();
    for(i=1 ; i<=n ; i++) redge[i].clear();
    for(i=1 ; i<=n ; i++) whi[i]=sz[i]=0; gr=org=ans=0;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


3. 회문인 부분 문자열


역시 작년에 비해 매우 어렵다. 다3 정도라고 생각. 복잡한 문제인 만큼 천천히 생각해보자. 해야 하는 것은

  • 우선 회문인 부분 문자열을 전부 뽑아낸다.
  • 그 중 조건을 만족하는 부분 문자열을 전부 뽑아낸다. (즉, 주어진 회문이 어떤 문자열에 포함되는지 판별해야 한다)
  • 그 후, 그 부분 문자열들을 사전순으로 정렬해서 $k$번째 것이 무엇인지를 파악해야 한다.

이제 각 단계를 어떻게 할 수 있을지 생각해보자.

  • APIO 2014 팰린드롬의 풀이를 생각하자. 길이 $n$ 문자열의 회문인 서로 다른 부분 문자열의 개수는 최대 $n$개다.
  • 이 시점에서 $k$의 제한은 페이크임을 알 수 있다. 또한, 회문을 모두 뽑는 것은 Manacher 알고리즘으로 가능하다.
  • 서로 다른 것을 뽑아냈는지를 확인해야 하는데, 이건 Rabin-Karp 해시로 가능하다. 충돌 안하게 모듈로 2개 적당히 잡자.
  • 위 koosaga 블로그 링크의 설명을 보면 사실 이 부분을 이분탐색 없이 할 수 있는데, 당시에는 이분탐색까지 덮었다.

이러면 1단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 2단계.

  • 어쨌든 후보들은 "특정 문자열의 부분문자열인 회문"들이다. 이제 이것들이 다른 문자열에도 포함되는지 확인해야 한다.
  • 그러면 세 문자열을 합친 (사이에 이상한 문자 껴넣고) 새 문자열을 만든 후, Suffix Array + LCP + Segment Tree를 적용한다.
  • 이 과정 자체는 꽤 티피컬한데 구현이 드럽게 힘들고 귀찮다. Suffix Array는 로그제곱으로 짜도 충분하다. 

이러면 2단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 마지막 단계.

  • 이제 부분문자열을 사전순 정렬해야 하는데, 단순하게 Suffix Array 상으로 정렬하면 안된다. (why?)
  • 제대로 정렬하려면 "이 회문을 prefix로 갖는 suffix 중 가장 Suffix Array에서 앞에 있는 것"을 찾을 필요가 있다.
  • 이를 위해서는 또 한 번 LCP + Segment Tree + 이분탐색을 적용하면 된다. 겁나 귀찮은데 해야함
  • 이제 회문들을 "SA 위치, 회문의 길이"라는 pair로 정렬하면 사전순 정렬이 됨을 확인할 수 있다. 끝.

가치가 있다고 생각해서, 디버깅 용 코드까지 전부 그대로 올린다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
const ll mod1=1561035197;
const ll mod2=1871313779;
const ll p1=27386137;
const ll p2=73186173;
 

int tree[333333], C=160000;
int k, L[3], d, LEN, FINCOUNT;
string s[3], S;
int len_odd[3][55555];
int len_tr[3][111111];
int len_ev[3][55555];
ll hsh1[3][55555];
ll hsh2[3][55555];
ll pt1[55555];
ll pt2[55555];
int LCP[155555];
int SA[155555];
int rk[155555];
int pos[155555];
int tp[155555];
vector<int> POS[3];
vector< pair< pair<int, int>, int> > indx;
// which string, location, length
pair<int, int> fin[155555];
// location in final string in (SA), length
set< pair<ll, ll> > EX; // already inserted hashes
 
bool cmp(const int U, const int V)
{
    if(pos[U]!=pos[V]) return pos[U]<pos[V];
    if(U+d<LEN && V+d<LEN) return pos[U+d]<pos[V+d];
    return U>V; // okay!
}
 
void calc_LCPSA(void)
{
    int i, j, c; LEN = S.length();
    for(i=0 ; i<LEN ; i++) pos[i]=S[i], SA[i]=i;
    for(d=1 ; d<=LEN ; d<<=1)
    {
        sort(SA, SA+LEN, cmp); tp[0]=0;
        for(i=1 ; i<LEN ; i++) tp[i]=tp[i-1]+cmp(SA[i-1], SA[i]);
        for(i=0 ; i<LEN ; i++) pos[SA[i]]=tp[i];
        if(tp[LEN-1]==LEN-1) break;
    }
    for(i=0 ; i<LEN ; i++) rk[SA[i]]=i;
    for(i=0, j=0 ; i<LEN ; i++, j=max(j-1, 0))
    {
        if(rk[i]==LEN-1) continue; c=SA[rk[i]+1];
        for( ; i+j<LEN && c+j<LEN && S[i+j]==S[c+j] ; j++);
        LCP[rk[i]]=j;
    }
}
 
void update(int loc, int v)
{
    loc+=C; tree[loc]=v;
    for( ; loc>1 ; loc>>=1)
        tree[loc>>1]=min(tree[loc], tree[loc^1]);
}
 
int query(int l, int r)
{
    int ret=1e9;
    for(l+=C, r+=C ; l<r ; l>>=1, r>>=1)
    {
        if(l&1) ret=min(ret, tree[l++]);
        if(r&1) ret=min(ret, tree[--r]);
    }
    return ret;
}
 
pair<ll, ll> hasher(int idx, int l, int r)
{
    // [l, r] = [0, r] - [0, l-1] * p^(r-l+1)
    if(l==0) return make_pair(hsh1[idx][r], hsh2[idx][r]);
    ll ret1=(hsh1[idx][r]-(hsh1[idx][l-1]*pt1[r-l+1]%mod1));
    if(ret1<0) ret1+=mod1;
    ll ret2=(hsh2[idx][r]-(hsh2[idx][l-1]*pt2[r-l+1])%mod2);
    if(ret2<0) ret2+=mod2;
    return make_pair(ret1, ret2);
}
 
void get_hash(int idx)
{
    ll cur1=0, cur2=0, i;
    for(i=0 ; i<s[idx].length() ; i++)
    {
        hsh1[idx][i]=(cur1*p1+(s[idx][i]-'a'+1))%mod1; cur1=hsh1[idx][i];
        hsh2[idx][i]=(cur2*p2+(s[idx][i]-'a'+1))%mod2; cur2=hsh2[idx][i];
    }
}
 
 
bool isok(int idx, int l, int r)
{
    pair<ll, ll> TT = hasher(idx, l, r);
    if(EX.count(TT)) return true;
    return false;
}
 
int getloc(int idx, int l)
{
    if(idx==0) return l;
    if(idx==1) return L[0]+1+l;
    if(idx==2) return L[0]+L[1]+2+l;
}
 
bool isinside(int idx, int RKloc, int goal)
{
    int cc=lower_bound(POS[idx].begin(), POS[idx].end(), RKloc)-POS[idx].begin();
    // POS[cc], POS[cc-1] trial
    if(cc < POS[idx].size())
    {
        // RKloc ~ cc distance
        int rv=query(RKloc, POS[idx][cc]);
        if(rv>=goal) return true;
    }
    if(cc-1 >=0)
    {
        int rv=query(POS[idx][cc-1], RKloc);
        if(rv>=goal) return true;
    }
    return false;
}
 
int get_front(int RKloc, int goal)
{
    int lef=0; int rig=RKloc-1; int best=RKloc, mid;
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(query(mid, RKloc)>=goal) best=mid, rig=mid-1;
        else lef=mid+1;
    }
    return best;
}
 
void add_work(int idx, int l, int r)
{
   // cout<<idx<<" "<<l<<" "<<r<<endl;
    pair<ll, ll> TT = hasher(idx, l, r); EX.insert(TT);
    // one should contain, other should not
    // [l, r] at idx
    int mylen=r-l+1; int myloc=rk[getloc(idx, l)];
    int others=0;
    if(isinside((idx+1)%3, myloc, mylen)) others++;
    if(isinside((idx+2)%3, myloc, mylen)) others++;
    int newmyloc=get_front(myloc, mylen);
    if(others==1)
    {
        FINCOUNT++;
        fin[FINCOUNT]=make_pair(newmyloc, mylen);
    }
}
 
void finwork(int idx)
{
    int i, j; // odd insert
    for(i=0 ; i<L[idx] ; i++)
    {
        int lef=1, rig=len_odd[idx][i], mid, best=0;
        while(lef<=rig)
        {
            mid=(lef+rig)/2;
            if(isok(idx, i-mid+1, i+mid-1)) best=mid, lef=mid+1;
            else rig=mid-1;
        }
        for(j=best+1 ; j<=len_odd[idx][i] ; j++)
            add_work(idx, i-j+1, i+j-1);
    }
    for(i=0 ; i<L[idx] ; i++)
    {
        if(len_ev[idx][i]==0) continue;
        int lef=1, rig=len_ev[idx][i], mid, best=0;
        while(lef<=rig)
        {
            mid=(lef+rig)/2;
            if(isok(idx, i-mid+1, i+mid)) best=mid, lef=mid+1;
            else rig=mid-1;
        }
        for(j=best+1 ; j<=len_ev[idx][i] ; j++)
            add_work(idx, i-j+1, i+j);
    }
}
 
// will do [l, r] form
 
void run_manacher(int idx)
{
    int i, l=1, r=1; L[idx]=s[idx].length();
    string Ns = "@" + s[idx] + "#";
    for(i=1 ; i<=L[idx] ; i++)
    {
        len_odd[idx][i]=min(r-i, len_odd[idx][l+(r-i)]);
        while(Ns[i-len_odd[idx][i]] == Ns[i+len_odd[idx][i]]) len_odd[idx][i]++;
        if(i+len_odd[idx][i]>r)
        {
            l=i-len_odd[idx][i];
            r=i+len_odd[idx][i];
        }
    }
    for(i=0 ; i<L[idx] ; i++) len_odd[idx][i]=len_odd[idx][i+1];
    string NNs = "{";
    for(i=0 ; i<L[idx] ; i++)
    {
        NNs.push_back(s[idx][i]);
        if(i!=L[idx]-1) NNs.push_back('#');
    }
    NNs.push_back('}'); // {a#b#c}
    ll t=NNs.length()-2; l=r=1;
    for(i=1 ; i<=t ; i++)
    {
        len_tr[idx][i]=min(r-i, len_tr[idx][l+(r-i)]);
        while(NNs[i-len_tr[idx][i]] == NNs[i+len_tr[idx][i]]) len_tr[idx][i]++;
        if(i+len_tr[idx][i]>r)
        {
            l=i-len_tr[idx][i];
            r=i+len_tr[idx][i];
        }
    }
    for(i=2 ; i<=t ; i+=2)
    {
        int lc=i/2-1;
        len_ev[idx][lc]=len_tr[idx][i]/2;
    }
}
 
void solve(void)
{
    FINCOUNT=0;
    int i, j; EX.clear();
    for(i=0 ; i<3 ; i++) POS[i].clear();
    memset(tree, 0, sizeof(tree)); indx.clear();
    cin>>s[0]>>s[1]>>s[2]>>k;
    memset(len_odd, 0, sizeof(len_odd));
    memset(len_ev, 0, sizeof(len_ev));
    memset(len_tr, 0, sizeof(len_tr));
    for(i=0 ; i<3 ; i++) get_hash(i);
    for(i=0 ; i<3 ; i++) run_manacher(i);
    /* testing manacher
    for(i=0 ; i<3 ; i++)
    {
        for(j=0 ; j<L[i] ; j++) cout<<len_odd[i][j]<<" "; cout<<"\n";
        for(j=0 ; j<L[i] ; j++) cout<<len_ev[i][j]<<" "; cout<<"\n";
    }
    */
    S = s[0] + '}' + s[1] + '}' + s[2];
    calc_LCPSA(); LEN=S.length();
    for(i=0 ; i<=L[0]-1 ; i++) POS[0].push_back(rk[i]);
    for(i=L[0]+1 ; i<=L[0]+L[1] ; i++) POS[1].push_back(rk[i]);
    for(i=L[0]+L[1]+2 ; i<=L[0]+L[1]+L[2]+1 ; i++) POS[2].push_back(rk[i]);
    for(i=0 ; i<3 ; i++) sort(POS[i].begin(), POS[i].end());
    for(i=0 ; i<=LEN-2 ; i++) update(i, LCP[i]);
 
    /* LCP, SA check
    for(i=0 ; i<=LEN-1 ; i++)
    {
        cout<<S.substr(SA[i], S.length())<<"\n";
        cout<<LCP[i]<<"\n";
    }
    */
    //cout<<"FINWORKSTART"<<"\n"; return;
    for(i=0 ; i<3 ; i++) finwork(i);
    sort(fin+1, fin+FINCOUNT+1);
    if(FINCOUNT<k) { cout<<-1<<endl; return; }
    int tt1=fin[k].first;
    int tt2=fin[k].second;
    for(i=0 ; i<tt2 ; i++) cout<<S[SA[tt1]+i];
    cout<<endl; return;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    pt1[0]=1; pt2[0]=1;
    for(i=1 ; i<=55550 ; i++) pt1[i]=(p1*pt1[i-1])%mod1;
    for(i=1 ; i<=55550 ; i++) pt2[i]=(p2*pt2[i-1])%mod2;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


5. 돌 옮기기


5-1을 긁는 것은 어렵지 않다. 상태 전이를 전부 파악하고 union-find를 돌리면 된다.

상태 전이를 효율적으로 하는 게 약간 헷갈릴 수 있는데, 비트마스킹을 잘 활용하면 $\mathcal{O}(n \cdot 2^n)$ 풀이를 얻는다.

뇌절을 한 흔적이 진짜 많이 보이는 코드를 짰다. 알아서 잘 해독하시길 ^~^;;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
 
int n, kt, msk1, msk2;
vector<int> edge[22];
int con[21][21];
int whi1[211111];
int whi2[211111];
int unionmask[1<<20];
int frst[1<<20];
int mymask[21];
int par[1<<20];
int actok[1<<20];
 
int find(int x)
{
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
 
void merge(int u, int v)
{
    if(!actok[u] || !actok[v]) return;
    u=find(u); v=find(v);
    if(u==v) return;
    par[u]=v; return;
}
 
void solve(void)
{
    bool actualwork=false;
    cin>>n; int i, j, k, u, v;
    memset(con, 0, sizeof(con));
    if(n<=20) { actualwork=true; }
    for(i=1 ; i<=n-1 ; i++)
    {
        cin>>u>>v; u--; v--;
        if(actualwork)
        {
            con[u][v]=1; con[v][u]=1;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
    }
    cin>>kt;
    for(i=1 ; i<=kt ; i++) cin>>whi1[i]>>whi2[i];
    for(i=1 ; i<=kt ; i++) whi1[i]--, whi2[i]--;
    if(!actualwork)
    {
        cout<<0<<endl;
        return;
    }
    memset(mymask, 0, sizeof(mymask));
    memset(unionmask, 0, sizeof(unionmask));
    memset(actok, 0, sizeof(actok)); actok[0]=1;
    for(i=0 ; i<n ; i++)
    {
        for(j=0 ; j<n ; j++)
        {
            if(con[i][j]) mymask[i]|=(1<<j);
        }
    }
    for(i=0 ; i<n ; i++) mymask[i]|=(1<<i);
    for(i=1 ; i<(1<<n) ; i++)
    {
        int cc=frst[i];
        unionmask[i]=unionmask[i^(1<<cc)]|mymask[cc];
    }
    for(i=1 ; i<(1<<n) ; i++)
    {
        int cc=frst[i];
        if(!actok[i^(1<<cc)]) continue;
        if((1<<cc)&(unionmask[i^(1<<cc)])) continue;
        actok[i]=1;
    }
    for(i=0 ; i<(1<<n) ; i++) par[i]=i;
    for(i=0 ; i<(1<<n) ; i++)
    {
        if(!actok[i]) continue;
        for(j=0 ; j<n ; j++)
        {
            if(!(i&(1<<j))) continue;
            int remmsk=i^(1<<j);
            for(k=0 ; k<edge[j].size() ; k++)
            {
                if(remmsk&(1<<edge[j][k])) continue;
                if(!(unionmask[remmsk]&(1<<edge[j][k])))
                    merge(i, remmsk|(1<<edge[j][k]));
            }
        }
    }
    int ans=0; int cur1=0; int cur2=0;
    for(i=1 ; i<=kt ; i++)
    {
        cur1|=(1<<whi1[i]);
        cur2|=(1<<whi2[i]);
        if(find(cur1)==find(cur2)) ans++;
    }
    for(i=0 ; i<n ; i++) edge[i].clear();
    cout<<ans<<endl;
}
 
 
int main(void)
{
    fio; int i, j, tc; cin>>tc;
    frst[0]=0; frst[1]=0;
    for(i=1 ; i<20 ; i++)
        for(j=1<<i ; j<(1<<(i+1)) ; j++) frst[j]=i;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


저작자표시 (새창열림)

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 1차 예선 풀이  (0) 2021.07.16
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22


매우 늦게 올린다. 결과는 6등으로, 예상보다는 매우 높았으나 여전히 만족스러운 결과는 아니었다. J를 풀지 못한것이 아쉬움.

작년의 팀과 멤버는 동일하다. rkm0959, junie, bjwj5505다. 내가 1년간 공부를 많이 한 건 맞지만, 정작 최근에는 CTF 참가 등으로 PS, CP에 집중하지 못해서 팀의 전체적인 실력이 강화된건지 퇴화된건지 좀 애매한 것 같다. 다른 팀원도 비슷하다. 일단 지금까지는 나쁘지 않게 하고 있는듯.

 

타임라인과 함께 간략한 설명을 붙이도록 하겠다. 모든 사람을 3인칭으로 명명하겠다.

  • 시작하자마자 문제 12개 모두 출력
  • 스코어보드 보니까 I가 0분컷으로 풀렸네? 진짜 쉽네?
  • rkm0959가 바로 컴퓨터 잡고 AC (5분)
  • 이때쯤 E도 퍼솔이 나왔고, 바로 rkm0959가 이어서 AC (8분)
  • bjwj5505는 이때 L을 읽고 있었고, junie는 앞쪽 문제를 읽는 중.
  • bjwj5505가 L을 구현했지만 WA 후 코드 프린트
  • rkm0959는 G를 보면서 수학 문제라고 생각을 했으나 매우 어려워보여서 대기중
  • 대신 K가 쉽다는 것을 확인하고, 풀이를 bjwj5505와 확인
  • rkm0959가 H의 풀이를 찾고, 정당성을 bjwj5505와 확인 
  • 그러다가 F가 쉬워보여서 rkm0959, junie가 해결 시도
  • bjwj5505가 L을 디버깅하고 있으며, rkm0959가 K를 짜기 시작
  • bjwj5505가 L을 고치고 AC (39분), rkm0959도 곧 K AC (46분)
  • bjwj5505, junie가 F의 풀이를 찾는동안 rkm0959 H 구현
  • F의 풀이를 찾고 AC (51분), H도 곧 AC (58분) - 1시간 6솔브 도달
  • 정확하게 기억은 안나지만 junie가 느린 J 풀이를 찾았음 (로그 2개)
  • 그러나 정확하게 풀이를 이해하고 있는 사람은 junie 혼자
  • bjwj5505, junie는 A의 해결에 집중. rkm0959는 B가 DP임을 확인
  • rkm0959가 D가 세그먼트 트리로 해결될 수 있는 문제임을 확인
  • A, B, D의 동시다발적 구현 + WA + 디버깅 파티 후 전부 AC (115, 133, 149분)
  • J를 고치려고 했고, "맞는" 풀이를 1분 전에 찾았으나 TLE. 똑떨....


저작자표시 (새창열림)

'PS > 대회 후기' 카테고리의 다른 글

ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
APIO 2020 Open Contest  (0) 2020.08.22

I participated in N1CTF as a member of Super Guesser. 4th Place :)

We solved all crypto problems, and it was a great collaboration of me and rbtree. 

The explanation will be very brief, because I don't have a lot of free time on my hands :( :(


VSS


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#!/usr/bin/python3
import qrcode  # https://github.com/lincolnloop/python-qrcode
import random
import os
from PIL import Image
from flag import FLAG
 
 
def vss22_gen(img):
    m, n = img.size
    share1, share2 = Image.new("L", (2*m, 2*n)), Image.new("L", (2*m, 2*n))
    image_data = img.getdata()
    flipped_coins = [int(bit) for bit in bin(random.getrandbits(m*n))[2:].zfill(m*n)]
    for idx, pixel in enumerate(image_data):
        i, j = idx//n, idx % n
        color0 = 0 if flipped_coins[idx] else 255
        color1 = 255 if flipped_coins[idx] else 0
        if pixel:
            share1.putpixel((2*j, 2*i), color0)
            share1.putpixel((2*j, 2*i+1), color0)
            share1.putpixel((2*j+1, 2*i), color1)
            share1.putpixel((2*j+1, 2*i+1), color1)
 
            share2.putpixel((2*j, 2*i), color0)
            share2.putpixel((2*j, 2*i+1), color0)
            share2.putpixel((2*j+1, 2*i), color1)
            share2.putpixel((2*j+1, 2*i+1), color1)
        else:
            share1.putpixel((2*j, 2*i), color0)
            share1.putpixel((2*j, 2*i+1), color0)
            share1.putpixel((2*j+1, 2*i), color1)
            share1.putpixel((2*j+1, 2*i+1), color1)
 
            share2.putpixel((2*j, 2*i), color1)
            share2.putpixel((2*j, 2*i+1), color1)
            share2.putpixel((2*j+1, 2*i), color0)
            share2.putpixel((2*j+1, 2*i+1), color0)
    share1.save('share1.png')
    share2.save('share2.png')
 
 
def vss22_superposition():
    share1 = Image.open('share1.png')
    share2 = Image.open('share2.png')
    res = Image.new("L", share1.size, 255)
    share1_data = share1.getdata()
    share2_data = share2.getdata()
    res.putdata([p1 & p2 for p1, p2 in zip(share1_data, share2_data)])
    res.save('result.png')
 
 
def main():
    qr = qrcode.QRCode(
        version=1,
        error_correction=qrcode.constants.ERROR_CORRECT_L,
        box_size=12,
        border=4,
    )
    qr.add_data(FLAG)
    qr.make(fit=True)
    img = qr.make_image(fill_color="black", back_color="white")
    vss22_gen(img._img)
    img.save('res.png')
    vss22_superposition()
 
 
if __name__ == '__main__':
    main()
 
cs


The vulnerability lies in the use of "getrandbits" - it's implemented using MT19937. This PRNG is known to be predictable after 624 output values are known. Also, if you try to generate a QR code with a sample flag, we can see that the first few rows of the generated output are all white. With this fact, we can retrieve the first few thousand bits generated, and we can predict the following bits generated by MT19937. Therefore, we can recover the original QR code. This solution (and code itself) is due to rbtree. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from mt import untemper
import random
from PIL import Image
 
img = Image.open('share2.png')
value = 0
for i in range(444):
    for j in range(444):
        value <<= 1
        value ^= 1 if 255 == img.getpixel((2 * j + 1, 2 * i)) else 0
 
tmp = value
values = []
for i in range(444 * 444 // 32):
    values.append(tmp & 0xffffffff)
    tmp >>= 32
 
mt_state = tuple(list(map(untemper, values[:624])) + [0])
random.setstate((3, mt_state, None))
 
# for i in range(444 * 444 // 32):
#     assert values[i] == random.getrandbits(32)
 
random.setstate((3, mt_state, None))
 
real_value = 0
for i in range(444 * 444 // 32):
    real_value ^= random.getrandbits(32) << (32 * i)
 
value ^= real_value
arr = [int(bit) for bit in bin(value)[2:].zfill(444 * 444)]
 
res = Image.new("L", (444, 444))
 
for i in range(444):
    for j in range(444):
        res.putpixel((j, i), 0 if arr[i * 444 + j] else 255)
    
res.save("res.png")
cs


FlagBot


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
import base64
from secret import flag
 
RECEIVER_NUM = 7
 
def generate_safecurve():
    while True:
        p = random_prime(2 ^ 256-1, False, 2 ^ 255)
        a = randint(-p, p)
        b = randint(-p, p)
 
        if 4*a^3 + 27*b^2 == 0:
            continue
 
        E = EllipticCurve(GF(p), [a, b])
 
        fac = list(factor(E.order()))
 
        # Prevent rho method
        if fac[-1][0] < 1 << 80:
            continue
 
        # Prevent transfer
        for k in range(1, 20):
            if (p ^ k - 1) % fac[-1][0] == 0:
                break
        else:
            return E
 
class Sender:
    def __init__(self, curves, receivers):
        self.secret = randint(1 << 254, 1 << 255)
        self.curves = curves
        self.receivers = receivers
        self.shared_secrets = [None for _ in range(len(receivers))]
 
    def setup_connections(self):
        for idx, receiver in enumerate(self.receivers):
            curve = self.curves[idx]
            print(f"curves[{idx}] : {curve}")
            g = self.curves[idx].gens()[0]
            print(f"g[{idx}] = {g.xy()}")
            receiver.set_curve(curve, g)
            public = self.secret * g
            print(f"S_pub[{idx}] = {public.xy()}")
            yours = receiver.key_exchange(public)
            print(f"R_pub[{idx}] = {yours.xy()}")
            self.shared_secrets[idx] = yours * self.secret
 
    def send_secret(self):
        msg = b'Hi, here is your flag: ' + flag
        for idx, receiver in enumerate(self.receivers):
            px = self.shared_secrets[idx].xy()[0]
            _hash = sha256(long_to_bytes(px)).digest()
            key = _hash[:16]
            iv = _hash[16:]
            encrypted_msg = base64.b64encode(AES.new(key, AES.MODE_CBC, iv).encrypt(pad(msg, 16)))
            print(f"encrypted_msg[{idx}] = {encrypted_msg}")
            receiver.receive(encrypted_msg)
 
 
class Receiver:
    def __init__(self):
        self.secret = randint(1 << 254, 1 << 255)
        self.curve = None
        self.g = None
        self.shared_secret = None
 
    def set_curve(self, curve, g):
        self.curve = curve
        self.g = g
 
    def key_exchange(self, yours):
        self.shared_secret = yours * self.secret
        return self.g * self.secret
 
    def receive(self, encrypted_msg):
        px = self.shared_secret.xy()[0]
        _hash = sha256(long_to_bytes(px)).digest()
        key = _hash[:16]
        iv = _hash[16:]
        msg = AES.new(key, AES.MODE_CBC, iv).decrypt(base64.b64decode(encrypted_msg))
        msg = unpad(msg, 16)
        assert msg.startswith(b'Hi, here is your flag: ')
 
 
receivers = [Receiver() for _ in range(RECEIVER_NUM)]
curves = [generate_safecurve() for _ in range(RECEIVER_NUM)]
 
A = Sender(curves, receivers)
A.setup_connections()
A.send_secret()
 
cs


This problem was solved by me, so I can give you a brief look inside my brain.

  • You can't really do anything with AES-CBC in this challenge
  • You can't really do anything with SHA256 anywhere
  • That means that we have to break the DH style shared secret generation
  • The secret key is reused every time, so that's the vulnerability
  • The curve generation only checks the existence of large primes, so small primes can exist

At this point, the solution was straightforward. For each small prime $p$ that divides the order of the elliptic curve used, we can find the value of the secret key $\pmod{p}$ by using Pohlig-Hellman approach. Combining these with CRT, we can recover $d$ since it is at most $2^{255}$. 

Since we do need to deal with primes of size around $10^{12}$, Baby-Step-Giant-Step is required. Just use Sage.


The below code finds all the shared secrets. The remaining parts of the problem are straightforward.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
cur_mod = 1
cur_val = 0
 
for i in range(0, 7):
    a = S[i][0]
    b = S[i][1]
    p = S[i][2]
    E = EllipticCurve(GF(p), [a, b])
    Ord = E.order()
    L = list(factor(Ord))
    GG = E(g[i])
    SS = E(S_pub[i])
    for pp, dd in L:
        if pp <= 10 ** 12 and dd == 1:
            Gp = (Ord // pp) * GG
            Sp = (Ord // pp) * SS
            tt = discrete_log(Sp, Gp, operation='+')
            cur_val = crt(cur_val, tt, cur_mod, pp)
            cur_mod = (cur_mod * pp) // gcd(pp, cur_mod)
    print("Done ", i)
    
print("[+] Secret: ", cur_val)
 
for i in range(0, 7):
    a = S[i][0]
    b = S[i][1]
    p = S[i][2]
    E = EllipticCurve(GF(p), [a, b])
    RR = E(R_pub[i])
    RES = RR * cur_val
    print(RES.xy()[0])
cs


curve


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/env sage
 
import signal, hashlib, string, random, os 
 
os.chdir(os.path.dirname(os.path.abspath(__file__)))
FLAG = open("./flag.txt", 'r').read()
ROUNDS = 30
 
def PoW():
  s = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
  h = hashlib.sha256(s.encode()).hexdigest()
  prefix = s[:16]
  print("sha256(%s+XXXX) == %s" % (prefix, h))
  c = input("Give me XXXX: ")
  if hashlib.sha256((prefix + c).encode()).hexdigest() == h:
    return True 
  return False
 
def chall():
  p = ZZ(input("P: "))  # of course we are using sage >= 9
  a = ZZ(input("A: "))
  b = ZZ(input("B: "))
 
  if not is_prime(p) or p.nbits() < 512:
    print("No bad parameters.")
    return
 
  E = EllipticCurve(GF(p), [a, b])
  if E.is_supersingular():
    print("No this is not good enough.")
    return
 
  q = E.order()
  x1 = ZZ(input("X1: "))
  y1 = ZZ(input("Y1: "))
  x2 = ZZ(input("X2: "))
  y2 = ZZ(input("Y2: "))
  G1 = E((x1, y1))
  G2 = E((x2, y2))
 
  for _ in range(ROUNDS):
    a0 = randint(1, q - 1)
    a1 = randint(1, q - 1)
 
    c = -1
    while c == -1 or c == a0 * a1:
      c = randint(1, q - 1)
 
    g0, g1 = G1 * a0, G2 * a1 
    c0, c1 = G1 * (a0 * a1), G1 * c
    b = randint(0, 1)
 
    if b == 0:
      print(g0, g1, c0)
    else:
      print(g0, g1, c1)
 
    choice = ZZ(input("Choice: "))
    if choice != b:
      print("Wrong choice.")
      return
 
  print(f"Thank you! Here's your reward: {FLAG}")
  return 
 
if __name__ == '__main__':
  if not PoW():
    print("Invalid PoW.")
    exit()
  signal.alarm(90)
 
  try:
    chall()
  except:
    print("oof...")
    exit()
 
 
cs


We struggled greatly on this challenge, despite finding the solution quite immediately. Here's the process.

  • $E$ is a large elliptic curve over a prime field, not supersingular
  • We select two points $G_1, G_2$ on the curve, and play a sort of Decisional Diffie-Hellman game.
  • Let's just fix $G = G_1 = G_2$ and see what we can do!
  • If the order of $G$ is small, say $t$ - we can recover $a_0, a_1 \pmod{t}$ easily. 
  • Therefore, we can directly calculate $a_0a_1G$ as well!
  • Check if this is equal to the third point given. If so, check $b=0$ and otherwise check $b=1$.
Now we do some analysis. 
  • If $b=0$ was chosen, this will give the correct answer with probability 1
  • If $b=1$ was chosen, we fail if $c \equiv a_0 a_1 \pmod{t}$, so we succeed with probability $1-1/t$
  • We do $30$ rounds, so $t$ shouldn't be too small (we want, say, $t> 50$)
  • Obviously we do need to solve the discrete logarithm on a group of order $t$, so we want small $t$

This leads to the following goal.

  • Find an elliptic curve that satisfies the server's desired conditions, with the order of the curve having a prime between $50$ and $400$

I think I took about 5 minutes until here, but the journey towards the flag for several reasons.

  • First, my initial code used random $p, a, b$, generate the curve, find the order, then check for small primes.
  • Seems good right? However, I tried to find $G$ using E.gens()[0] * (Order // small_prime)
  • This obviously takes infinite time, and my computer was on the verge of dying because of it
  • I realized the problem and replaced it by generating any point with Tonelli-Shanks and multiplying it by Order // small_prime

So I thought I was done here. After sending the parameters, I realized that I was not done here. Why?

  • The server calculates the order of the elliptic curve as well
  • While order calculation is done in polynomial time, it's still slow with 512 bit curve parameters
  • Therefore, the server times out, and I can't solve the problem

So I thought I was done here, in a different meaning. After solving the remaining challs, I tried the following.

  • Simply try the curves of the form $y^2 = x^3 + b$.

This worked, as the order calculation was done much faster. The challenge was solved.

The parameter finding and solution finding was done by me, and the programming was done by rbtree.


I learned a lot from solving this problem :) I'm still inexperienced, lots of studying to do... 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pr = []
for x in range(50, 200):
    if x in Primes():
        pr.append(x)
while True:
    p = random_prime(2 ** 512, False, 2 ** 511)
    if p % 3 == 2: ## in this case, y^2 = x^3 + b is guaranteed to be supersingular
        continue
    d = randint(1, p-1)
    E = EllipticCurve(GF(p), [0, d])
    if E.is_supersingular() == True:
        continue
    print(p)
    L = E.order()
    for cc in pr:
        if L % cc == 0:
            print(p, d, cc, L)
            break
 
## find any point on the elliptic curve
for u in range(1, 100):
    goal = (u ** 3 + a * u + b) % p
    if pow(goal, (p-1) // 2, p) == 1:
        v = tonelli(goal, p) ## sqrt, so you can directly use sage
        G = E(u, v)
        break
 
## hope that G is nonzero
G = G * (Ord // pr)
G1 = G
G2 = G
 
## this ends parameter generation
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
## by rbtree
 
from pwn import *
import string
import itertools
 
conn = remote('47.242.140.57', 9998)
conn.settimeout(None)
 
# PoW
 
challenge = conn.recvline().strip()
print(challenge)
prefix = challenge[7:7+16]
h = challenge.split()[-1]
charset = (string.ascii_letters + string.digits).encode()
for suffix in itertools.product(charset, repeat=4):
    if hashlib.sha256(prefix+bytes(suffix)).hexdigest() == h.decode():
        conn.sendlineafter(b'Give me XXXX: ', bytes(suffix))
        break
print("PoW Done")
 
p = 11572562087281212077294341316763410822093276559896892655806738743748493229131824454041157658617469079306138012813995393545636120267619633658087398895787057 
a = 0
b = 587626359248673832094266933340735482471140319598254235432650868938827936103013631493279303809976008538035914917596142929543705518144408460458007005924570
pr = 97
order = 11572562087281212077294341316763410822093276559896892655806738743748493229131918957581964494921602014693617723606720177358361724985583223555103419211299648
 
Gs = [] ## bunch of points (G, 2G, ... 97G)
print(len(Gs))
 
def get_points():
    points_s = conn.recvline().decode().strip()[1:-1].split(') (')
    points = []
    for point_s in points_s:
        point = tuple(int(v.strip()) for v in point_s.split(':')[:2])
        points.append(point)
    return points
 
conn.sendlineafter(b'P: ', str(p))
conn.sendlineafter(b'A: ', str(a))
conn.sendlineafter(b'B: ', str(b))
conn.sendlineafter(b'X1: ', str(Gs[0][0]))
conn.sendlineafter(b'Y1: ', str(Gs[0][1]))
conn.sendlineafter(b'X2: ', str(Gs[0][0]))
conn.sendlineafter(b'Y2: ', str(Gs[0][1]))
 
print("Parameter Sent")
 
for _ in range(30):
    points = get_points()
 
    for i in range(96):
        if points[0] == Gs[i]:
            a = i + 1
            break
 
    for i in range(96):
        if points[1] == Gs[i]:
            b = i + 1
            break
 
    to_send = 0 if Gs[(a * b % 97) - 1] == points[2] else 1
    conn.sendlineafter(b'Choice: ', str(to_send))
 
conn.interactive()
cs


BabyProof


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from hashlib import sha256
 
from Crypto.Util.number import getRandomRange
from Crypto.PublicKey import DSA
 
from secret import proof_of_work, flag
 
 
x = int.from_bytes(flag, 'big')
assert x.bit_length() == 247
 
 
def baby_proof():
    key = DSA.generate(3072)  # It takes time to generate, plz be patient...
    p, q, g = key.domain()
    y = pow(g, x, p)
 
    v = getRandomRange(1, x)
    t = pow(g, v, p)
 
    gyt = b"".join(
        map(
            lambda x: int.to_bytes(len(str(x)), 4, 'big') + str(x).encode(),
            (g, y, t)
        ))
    c = int.from_bytes(sha256(gyt).digest(), 'big')
    r = (v - c*x) % q
 
    print("I want to prove to you that I am in the knowledge of the discrete "
          "logarithm x that satisfies g^x = y modulo p, with the order of g "
          "modulo p being q.")
    print("However, I don't want to leak any information about x.")
    print("So, I use a non-interactive zero-knowledge proof for my purpose.")
    print("=================================================================")
    print("Here is my proof: ")
    print("Firstly, I choose a random (secret) v and compute t = g^v in Zq.")
    print("Secondly, I compute c = SHA256(g, y, t).")
    print("Then, I compute r = v - cx modulo q.")
    print("Finally, I will send you my proof (t, r).")
    print("You can check it by determining whether t == g^r * y^c or not.")
    print("Since there's negligible probability that I could forge the value "
          "r, you should believe that I really have knowledge of x.")
    print(g, y, p, q, t, r, sep="\n")
 
 
if __name__ == "__main__":
    if proof_of_work():
        baby_proof()
cs


The key here is that $x$ is quite small compared to $2^{256}$, and $v$ is selected in $[1, x]$. 

Given the printed parameters, we can directly obtain the value of $c$ as well. We see that $$ cx \equiv v - r \pmod{q}, \quad 1 \le v \le x $$ Since $x$'s bit length is $247$, we get $1 \le v \le 2^{247}$ and can write something like $$ cx \pmod{q} \approx -r + 2^{246} \pmod{q} $$ This is an instance of Hidden Number Problem, so just gather a lot of these information and solve it.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
d = 60 ## get 60 instances
M = Matrix(ZZ, d+1, d+1)
for i in range(0, d):
    M[0, i] = cs[i]
M[0, d] = 1
for i in range(0, d):
    M[i+1, i] = qs[i]
 
Target = [0] * (d+1)
for i in range(0, d):
    Target[i] = (2 ** 246) - rs[i]
Target[d] = (2 ** 246)
 
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
x = TT[d]
print(x)
print(bytes.fromhex(hex(x)[2:]))
cs


easyRSA?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
import numpy as np
 
mark = 3**66
 
def get_random_prime():
    total = 0
    for i in range(5):
        total += mark**i * getRandomNBitInteger(32)
    fac = str(factor(total)).split(" * ")
    return int(fac[-1])
 
def get_B(size):
    x = np.random.normal(0, 16, size)
    return np.rint(x)
 
p = get_random_prime()
q = get_random_prime()
N = p * q
e = 127
 
flag = b"N1CTF{************************************}"
secret = np.array(list(flag))
 
upper = 152989197224467
A = np.random.randint(281474976710655, size=(e, 43))
B = get_B(size=e).astype(np.int64)
linear = (A.dot(secret) + B) % upper
 
result = []
for l in linear:
    result.append(pow(l, e, N))
 
print(result)
print(N)
np.save("A.npy", A)
 
cs


Looking at the problem, we see that we need to do the following

  • Factorize $N$ using the vulnerable random prime generator, and recover the array "linear"
  • Solve the instance of LWE by using the fact that secret vector (the flag) is small as well

We first focus on the first part. I actually thought about coppersmith method, but I couldn't get it to work.

I already have an experience in wasting time with coppersmith approach, (sharsable) so I stopped attempting.


rbtree noted that there is a polynomial $f$ with small coefficients, degree 8, and $f(3^{66}) \equiv 0 \pmod{N}$.

This is because for each $p, q$, there's a degree 4 polynomial with small coefficients that vanishes at $3^{66}$ modulo that prime.

If we multiply the two degree 4 polynomials, we arrive at the described polynomial of degree 8.

He then suggested using a lattice to find this polynomial. This was an excellent idea!


Since we want a small-coefficient-linear-combination of $3^{66 \cdot 0}, 3^{66 \cdot 1}, \cdots , 3^{66 \cdot 8}$ that vanishes to zero, we must use scaling, as I did in sharsable. Check the code for technical details. As I do usually, I used Babai's closest vector algorithm. We can expect $f$ to be factorized into two polynomials of degree 4. By calculating each polynomial at $3^{66}$ and taking GCDs, we can retrieve $p, q$. This completes Part 1. 


For Part 2, we need to solve the LWE problem. This is hard in general, but we know that the secret vector is small as well. 

Of course, LWE problem can be modeled as CVP problem, and we use the "secret vector is small" fact here as well.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
## Step 1 : Factorization of N
rat = 2 ** 1000 
## scaling : super large to force zero in the first column
 
for i in range(0, 9):
    M[i, 0] = (3 ** (66 * i)) * rat
M[9, 0] = n * rat
for i in range(0, 9):
    M[i, i+1] = 1
 
Target = [0] * 10
for i in range(1, 10):
    Target[i] = (2 ** 64)
 
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
P.<x> = PolynomialRing(ZZ)
f = 0
for i in range(1, 10):
    f = f + TT[i] * x^(i-1)
print(f.factor())
## (2187594805*x^4 + 2330453070*x^3 + 2454571743*x^2 + 2172951063*x + 3997404950) 
## (3053645990*x^4 + 3025986779*x^3 + 2956649421*x^2 + 3181401791*x + 4085160459)
 
cc = 0
cc += 2187594805 * (3 ** (66 * 4))
cc += 2330453070 * (3 ** (66 * 3))
cc += 2454571743 * (3 ** (66 * 2))
cc += 2172951063 * (3 ** (66 * 1))
cc += 3997404950 * (3 ** (66 * 0))
 
p = gcd(cc, n)
print(p)
print(n // p)
print(n % p)
 
## Step 2 : housekeeping stuff
## res in res.txt, A in A.npy
p = 122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497
q = 268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533
e = 127
n = p * q
phi = (p-1) * (q-1)
d = inverse(e, phi)
 
cv = []
for x in res:
    cv.append(pow(x, d, n))
 
print(cv)
 
np.set_printoptions(threshold=sys.maxsize)
A = np.load("A.npy")
A = np.ndarray.tolist(A)
print(A)
 
## Step 3 : LWE with CVP
mod = 152989197224467
 
sel = 15 ## sel can be large as 127, but that's too slow
M = Matrix(ZZ, sel + 43, sel + 43)
for i in range(0, 43):
    for j in range(0, sel):
        M[i, j] = A[j][i]
    M[i, sel + i] = 1
for i in range(43, 43+sel):
    M[i, i-43] = mod
Target = [0] * (sel + 43)
for i in range(0, sel):
    Target[i] = cv[i] - 8
for i in range(sel, sel + 43):
    Target[i] = 80 ## printable
 
Target = vector(Target)
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
print(TT)
 
res = ""
for i in range(sel, sel+43):
    res += chr(TT[i])
 
print(res)
 
cs


저작자표시 (새창열림)

'CTF' 카테고리의 다른 글

TetCTF 2021 Crypto Writeups  (1) 2021.01.03
PBCTF 2020 Crypto Writeups  (1) 2020.12.07
SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
CryptoHack All Solve  (3) 2020.09.30
TokyoWesternCTF 2020 Crypto Write-Ups  (2) 2020.09.20

main.pdf


저작자표시 (새창열림)

'Cryptography' 카테고리의 다른 글

Schnorr's Protocol & Signature  (0) 2021.02.13
Diophantine Argument of Knowledge  (4) 2021.01.20
암호론 논문 리딩 #4: The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli  (0) 2020.06.25
암호론 논문 리딩 #3: Twenty Years of Attacks on the RSA Cryptosystem  (1) 2020.04.02
암호론 논문 리딩 #2: Even-Mansour Scheme  (5) 2020.03.28

I participated in SECCON 2020 Online CTF as a member of HangulSarang. We got 1st place :)

Hangul Day is also my birthday, so that's something I guess :D


The competition collided with ACM-ICPC quals, so I had to start solving at like 7PM. (4 hours late)


During that 4 hours, my teammate solved "This is RSA", which is solved using that each byte can be only 0x30 to 0x39. After that, we can compute solutions in $\pmod{2^k}$ and move upwards using recursion. It was the easiest crypto problem in this CTF, (and the solver wasn't me) so I think I don't need to explain further. The other four crypto problems were quite good, challenging, and very enjoyable, so I will describe my thought process as well. Huge thanks to the problem authors for creating these challenges. :D


koharu


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
while True:
    p = random_prime(1<<64)
    if is_prime((p+1) // 2):
        break
 
with open("flag.txt", "rb") as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")
 
 
PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break
 
while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break
 
NP = p**P.degree()
NQ = p**Q.degree()
 
while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break
 
PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1
 
print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)
 
 
cs


The code screams "quadratic residue", and it's similar to bitcrypto in InterKosenCTF. (write-up in this blog)

The only difference is that we are not using large primes, but polynomials in $GF(p)[x]$. This is already weak. 

The reason is that we can easily factorize polynomials in $GF(p)$. We can ask Sage to do it for us :)

Now we can determine whether a given polynomial is a quadratic residue or not. Combine this to get the flag.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p = 4832823609987476353
F.<x> = PolynomialRing(GF(p))
PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + 2532248969060743840*x^125 + 157159147928168793*x^124 + 1165294508775017303*x^123 + 54498477947855453*x^122 + 564670281176250610*x^121 + 4686383084102262935*x^120 + 4798143559496813901*x^119 + 2373759188753852032*x^118 + 3458843219210551923*x^117 + 3389173528515223367*x^116 + 3175114023644661971*x^115 + 2668820643276713526*x^114 + 1644657084961816584*x^113 + 1949973045428555331*x^112 + 2314884799372359978*x^111 + 1614909032209480656*x^110 + 3706101120120959039*x^109 + 1443476119293487220*x^108 + 507539962924420368*x^107 + 2851578707595377440*x^106 + 2660707099322090529*x^105 + 2275120831055073492*x^104 + 4642644673121099806*x^103 + 780741129747777966*x^102 + 3824963851609159359*x^101 + 1445016816241934269*x^100 + 4706494165496469049*x^99 + 91460120231848540*x^98 + 2033361932245472629*x^97 + 4657205830657809352*x^96 + 627579987075662316*x^95 + 2638155163726745709*x^94 + 773248040814209977*x^93 + 4426134463977473378*x^92 + 1748835523159978170*x^91 + 2545886874835388035*x^90 + 4318027045196127783*x^89 + 529092995613843935*x^88 + 37621695756851259*x^87 + 724317479549357114*x^86 + 235872728824864204*x^85 + 1409136599403563059*x^84 + 984842291673572708*x^83 + 1000642979551429427*x^82 + 2599952022893048437*x^81 + 33489199855748196*x^80 + 2138571356326295553*x^79 + 357904099457660261*x^78 + 1388605866466399741*x^77 + 2123614714168365349*x^76 + 1296407111118101425*x^75 + 3175149128196009486*x^74 + 4407671566428651830*x^73 + 3653949472018283742*x^72 + 2150666969917189331*x^71 + 2425834809198809729*x^70 + 202017664024051124*x^69 + 4656859267960293209*x^68 + 95544718007904685*x^67 + 551963924883187932*x^66 + 1220133766833256737*x^65 + 418789913385574936*x^64 + 3140425594489130574*x^63 + 653426727346469624*x^62 + 2168508737790275670*x^61 + 1350675684196344669*x^60 + 86970043713584944*x^59 + 3125122442296761190*x^58 + 1691082709013935740*x^57 + 14954357710735056*x^56 + 1951640599446313225*x^55 + 3057759244385615044*x^54 + 2842299299534580663*x^53 + 60118912044101305*x^52 + 3791459205438092561*x^51 + 3961025931327708139*x^50 + 3352223936735193809*x^49 + 458087980170556413*x^48 + 303065746752057039*x^47 + 270269323703788403*x^46 + 3435561048914221019*x^45 + 244980776425782882*x^44 + 1756735569264346021*x^43 + 1049402079460555244*x^42 + 1181023304135761892*x^41 + 2480814159047994100*x^40 + 3359295278584507081*x^39 + 1031815312165038169*x^38 + 2284789340145013050*x^37 + 2507227047920435897*x^36 + 4212274843760760739*x^35 + 1874163516348469998*x^34 + 4184876619139253979*x^33 + 2454055493008310058*x^32 + 4810631595605704078*x^31 + 2705618732956794205*x^30 + 4588422028499215564*x^29 + 1362947071518584749*x^28 + 200625668549982104*x^27 + 4162225127389871946*x^26 + 3671964574429446847*x^25 + 497776717675475749*x^24 + 3171362364421276926*x^23 + 4040585504650270495*x^22 + 55143980688943936*x^21 + 1680279432641096886*x^20 + 1141249890787830167*x^19 + 1632171956841566025*x^18 + 4489792289887403690*x^17 + 72863318133800422*x^16 + 3512973315964270180*x^15 + 1880837549990432714*x^14 + 629108155937185931*x^13 + 605563550674482475*x^12 + 3125052390516629852*x^11 + 3434353753938817079*x^10 + 2199180089161294937*x^9 + 4128993677150612079*x^8 + 875038461592559534*x^7 + 1344699457303227348*x^6 + 3605318452000064928*x^5 + 1825112182884559504*x^4 + 4214849563830404245*x^3 + 3018789469914511583*x^2 + 4256870332540451928*x + 3478109193918270445
R = 10529800129354981*x^64 + 4658846300069202283*x^63 + 1343603688498785880*x^62 + 77535778799313918*x^61 + 3909004297055292936*x^60 + 1574062357470841720*x^59 + 2255026177942473610*x^58 + 2913895405335010190*x^57 + 910153010204378491*x^56 + 4823161627331431259*x^55 + 4314926186108070132*x^54 + 3776194104903441585*x^53 + 4218241384907734159*x^52 + 2928099962473177675*x^51 + 3620663369166129209*x^50 + 4671199329340054093*x^49 + 2953252709684913819*x^48 + 1470028746745533363*x^47 + 393509208258687360*x^46 + 2631641671658679748*x^45 + 4823463900549231672*x^44 + 22025139085889956*x^43 + 3905072220448754367*x^42 + 3525611426409694274*x^41 + 1087703571442464513*x^40 + 983613039355879671*x^39 + 2292836760450398296*x^38 + 2429042383184252432*x^37 + 4241866215562144008*x^36 + 3567456235250802214*x^35 + 289826756486726727*x^34 + 3070079221437908111*x^33 + 3164478508626375897*x^32 + 4028195041942471423*x^31 + 1611744044712776226*x^30 + 682031605725048858*x^29 + 2334009162012075842*x^28 + 1056698946696323305*x^27 + 1193918408929283326*x^26 + 1546583097398597126*x^25 + 632624061599387394*x^24 + 3924194912006864689*x^23 + 836241738980292724*x^22 + 2019639656826418643*x^21 + 646182266409329495*x^20 + 3568811299250961381*x^19 + 4024124722170180214*x^18 + 2765626713849083593*x^17 + 830125243533734584*x^16 + 3773807917205041413*x^15 + 4579071273569219071*x^14 + 4169012455774239610*x^13 + 2779202281389813792*x^12 + 1668767138196611027*x^11 + 3668902156196312613*x^10 + 2118966174503976203*x^9 + 2876683474352545557*x^8 + 4749450906737437136*x^7 + 2048549559963146669*x^6 + 2337906091414592304*x^5 + 3234395871197583532*x^4 + 624006023034932764*x^3 + 1020142386943254010*x^2 + 4346889740151908150*x + 2337193413394346074
c = []
P = (x^64 + 2705838326093066801*x^63 + 1861763125820805142*x^62 + 1919270169024731361*x^61 + 728192979251886197*x^60 + 3703504742135431297*x^59 + 608310330267197202*x^58 + 677522369546315305*x^57 + 45111914222503868*x^56 + 3231090245423531905*x^55 + 4439626063971680541*x^54 + 264779255326565930*x^53 + 943573327092647824*x^52 + 3642035360519473519*x^51 + 4624797912514728904*x^50 + 815168423497123035*x^49 + 2058290770523809000*x^48 + 4368972367338353614*x^47 + 1102710837251449034*x^46 + 1838631000574578462*x^45 + 1550208773716319692*x^44 + 4479635398032603580*x^43 + 2547505501081696879*x^42 + 4733577241261296757*x^41 + 1459044726889718801*x^40 + 4736670792998507780*x^39 + 3481084975759672453*x^38 + 4491590348438475003*x^37 + 4286960290474469508*x^36 + 2519824328645383346*x^35 + 722570560813334776*x^34 + 3203376079187925593*x^33 + 2137713042365333594*x^32 + 2529680584881125743*x^31 + 881878615185959251*x^30 + 2648895700342509353*x^29 + 3093613170934869890*x^28 + 1839149659686122740*x^27 + 901352037355979824*x^26 + 3079388294575162468*x^25 + 4316897640303347156*x^24 + 3768144827267250554*x^23 + 1585476600468626452*x^22 + 2408180731465025131*x^21 + 2754322334879778466*x^20 + 1965864600205111832*x^19 + 3016989393277154199*x^18 + 993850365653028982*x^17 + 1661221355151932055*x^16 + 2141520480611688809*x^15 + 636670112723307258*x^14 + 1200822100799196786*x^13 + 2223563845526420680*x^12 + 3134534498746508642*x^11 + 1820327632682349699*x^10 + 4628418849122802568*x^9 + 3731553570235638636*x^8 + 1636534607043587796*x^7 + 1007966122754856335*x^6 + 3571611463638839115*x^5 + 4733247188903796455*x^4 + 3512981852602786831*x^3 + 1560667366459827025*x^2 + 1113839338158290233*x + 4011393002849553527)
Q = (x^64 + 2776622066009961678*x^63 + 1020248994272362724*x^62 + 1812889731002797017*x^61 + 3946133096396475132*x^60 + 1064362775780462120*x^59 + 4267166204741846229*x^58 + 4461168980925876722*x^57 + 3701193932757315736*x^56 + 4004259984657770019*x^55 + 2566923830139634808*x^54 + 2958380329303059106*x^53 + 4642913814072279374*x^52 + 713990683265973444*x^51 + 2282781718594249732*x^50 + 1691679008052617295*x^49 + 4723620313305465430*x^48 + 4052669689859242595*x^47 + 4607757741831461143*x^46 + 3048879536065529044*x^45 + 2012013680568798151*x^44 + 2125237235418450484*x^43 + 2622384625077739224*x^42 + 710661875195936255*x^41 + 375897308743404378*x^40 + 3253268532586707019*x^39 + 3759767504239334681*x^38 + 2945194932005180334*x^37 + 1316716161821289054*x^36 + 2210075866459201344*x^35 + 3421886933443572088*x^34 + 2124192011313760002*x^33 + 3183242335232871177*x^32 + 4722704310996441203*x^31 + 1640862527872462873*x^30 + 292078618156889354*x^29 + 3970255331239899451*x^28 + 290424178543927660*x^27 + 3979382049081683506*x^26 + 3341058157535181184*x^25 + 1891458780676141416*x^24 + 4585931142037966308*x^23 + 2621586816910493860*x^22 + 4526407296014662985*x^21 + 3345825075365423903*x^20 + 433595205227433076*x^19 + 3510443356995660854*x^18 + 1469161865274264871*x^17 + 1968552305256496645*x^16 + 1902262417167822976*x^15 + 3211385257470450715*x^14 + 259183745852362935*x^13 + 1368548986536267534*x^12 + 3726482530039832086*x^11 + 1196244075361051439*x^10 + 3346319329141804238*x^9 + 2362535635162047034*x^8 + 2131037938034625812*x^7 + 3970887869581347678*x^6 + 4428522899784697485*x^5 + 2482987898184812388*x^4 + 3180131420672415636*x^3 + 4690602932003451909*x^2 + 2572790493146370264*x + 802891458181310745)
cv = (p ** 64 - 1) // 2
fin = 0
add = 1
for ply in c:
    Pv = power_mod(ply, cv, P)
    Qv = power_mod(ply, cv, Q)
    if Pv == 1 and Qv == 1:
        fin += add
    add = add * 2
print(fin) ## long to bytes here
cs


urara


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from flag import flag
 
p = random_prime(1 << 1024)
q = random_prime(1 << 1024)
n = p * q
 
print("n =", n)
 
# ---
 
x = int.from_bytes(flag, "big")
y = randint(0, n-1)
 
a = randint(0, n-1)
b = (y^2 - (x^3 + a*x)) % n
 
EC = EllipticCurve(Zmod(n), [a, b])
 
P = EC((x, y))
Q = 2 * P
 
print("a, b =", [a, b])
print("Q =", Q.xy())
 
# ---
 
m = int.from_bytes(flag, "big")
t = randint(0, n-1)
 
c = power_mod(m + t, 65537, n)
print("t =", t)
print("c =", c)
 
cs


Very concise problem. We are given $t, e, n$ and $(m+t)^e \pmod{n}$, and a point is double the point with [$x$-coordinate equal to $m$] [which lies on the elliptic curve $y^2 = x^3 + ax + b$]. I broke that sentence up into pieces because it's pretty long and confusing. So anyways, doing actually elliptic curve stuff seems nearly impossible with the lack of hints we have, and we have a huge hint in $(m+t)^e \pmod{n}$. If we have another polynomial equation about $m$ in $\mathbb{Z}_n[x]$, we can solve this problem using polynomial GCD. (Franklin-Reiter related message attack, like padrsa in InterKosen CTF) Of course, we do have another polynomial equation! Directly using the doubling formula, we have $$ (3m^2 + a)^2 - (2m + Q_x)(4(m^3 + am+b)) \equiv 0 \pmod{n}$$ which is the type of equation we want. Write polynomial GCD, and we can easily find $m$. Again, note that if we encounter a problem while performing standard Euclidean Algorithm, it's because the leading coefficient has a non-trivial GCD with $n$. In this case, we can just factorize $n$ to solve the problem. I was stuck in sharsable for so long before solving this one, so I got some energy from it :D 


For the implementation of polynomial GCD, refer to the write-up of the problem padrsa. 


1
2
3
4
5
6
K = Zmod(n)
P.<x> = PolynomialRing(K, implementation='NTL')
f = (3 * x^2 + a)^2 - (2*x + Qx) *(4*(x^3 + a*x+b))
g = power_mod(x + t, 65537, f) - c
print(GCD(f, g, n))
## the remaining details are trivial
cs


sharsable


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import getPrime, GCD
from flag import FLAG
import random
 
def egcd(a, b):
    r0, r1 = a, b
    s0, s1 = 1, 0
    t0, t1 = 0, 1
    while r1 > 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return s0, t0
 
def generateKey():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p-1)*(q-1)
 
    while True:
        d1 = getPrime(int(n.bit_length()*0.16))
        e1 = random.randint(1, phi)
        ed1 = e1 * d1 % phi
 
        d2 = getPrime(int(n.bit_length()*0.16))
        e2, k = egcd(d2, phi)
        e2 = e2 * (phi + 1 - ed1) % phi
        ed2 = e2 * d2 % phi
 
        if GCD(e1, e2) > 10:
            break
 
    assert((ed1 + ed2) % phi == 1)
 
    return (n, (e1, d1), (e2, d2))
 
n, A, B = generateKey()
M = int.from_bytes(FLAG, 'big')
C1 = pow(M, A[0], n)
C2 = pow(M, B[0], n)
assert(pow(C1, A[1], n) * pow(C2, B[1], n) % n == M)
 
import json
print(json.dumps({
    "n": n,
    "A": (A[0], C1),
    "B": (B[0], C2),
    #"d": (A[1], B[1]), # for debug
    }))
 
cs


The code looks convoluted, but it can be compressed (without information loss) into the following results:

  • $d_1, d_2$ are quite small, around $n^{0.16}$. 
  • $e_1d_1 + e_2d_2 \equiv 1 \pmod{\phi(n)}$.
  • We know $e_1, e_2, n$, but we can't use common modulus attack due to $\text{gcd}(e_1, e_2) = 11$.

I didn't even realize we could use common modulus attack here, but that was okay since it doesn't give us useful information anyway. The key clearly lies in the small $d_1, d_2$. At first, my thought was headed to the Wiener's Attack, which I think is justifiable because that attack works with small $d$ as well. Of course, it's hard (if not impossible) to use the continued fraction idea directly. After reading up on some generalizations of Wiener's Attacks, I thought this problem was related to the coppersmith attack. I tried weird stuff like 3-variable coppersmith but it all failed pretty badly. That led to me solving this problem the last out of the four I solved. The idea of the last problem helped me :)


We begin by writing (note that this kind of manipulation is done in Wiener's Attack as well) $$e_1 d_1 + e_2 d_2 = k \phi(n) + 1 = k(n-p-q+1) + 1 \equiv -k(p+q-1) + 1 \pmod{n}$$ We may now note that $k$ is probably around $n^{0.16}$ as well, so the RHS is around $-n^{0.66}$ multiplied by some constant. 


Okay, so we want $d_1, d_2$ to be around $n^{0.16}$, and $e_1d_1 + e_2d_2 \pmod{n}$ to be around $-n^{0.66} \cdot c$ for some "reasonable" constant $c$. Let's first decide the range of $c$ we will look for. We can expect $k$ to be $0.4 \cdot n^{0.16}$ to $2 \cdot n^{0.16}$. We can expect $p+q$ to be $2 \cdot n^{0.5}$ to $3/\sqrt{2} \cdot n^{0.5}$. Combining, we can get something like $c \in [0.8, 4]$. Note that I'm using a lot of handwaving. Now we will fix $c$. 


The result? We have goal values for $d_1, d_2, e_1d_1 + e_2d_2 \pmod{n}$. Sounds like CVP to me now. 

Indeed, we can work this as a CVP with the lattice generated by $$ [e_1, 1, 0], \quad [e_2, 0, 1], \quad [n, 0, 0] $$ and making the result vector as close as possible to $$ [-c \cdot n^{0.66}, n^{0.16}, n^{0.16} ] $$ Here's a problem. The scale between the first column and the next two columns are off by $n^{0.5}$. If we run CVP now, it'll probably ignore the $n^{0.16}$ condition in order to get similar values for the first column. At least, that's what I thought :D 


Therefore, we rescale. We will work with the lattice generated by $$  [e_1, n^{0.5}, 0], \quad [e_2, 0, n^{0.5}], \quad [n, 0, 0] $$ and making our result vector as close as possible to $$ [-c \cdot n^{0.66}, n^{0.66}, n^{0.66} ] $$ which sounds more reasonable. If we run the CVP algorithm, (Babai's) we will have our candidate values for $d_1, d_2$. 

If correct, we will have that $e_1d_1 + e_2d_2 - 1$ is a product of $\phi(n)$, so we can finish easily. So, how do we find the right $c$ to use?


Simple. Just try a whole bunch of them. Refer to the code below for details.  


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small 
    
n  = 142793817321992828777925840162504083304079023834001118099549928854335392622287928254035247188624975743042449746066633491912316354241339908190889792327014012472372654378644158878787350693992259970146885854641856991605625756536504266728483088687985429310233421251081614258665472164668993082471923690196082829593
e1 = 82815162880874815458042429141267540989513396527359063805652845923737062346339641683097075730151688566721221542188377672708478777831586255213972947470222613130635483227797717393291856129771004300757155687587305350059401683671715424063527610425941387424425367153041852997937972925839362190900175155479532582934
C1 = 108072697038795075732704334514926058617161875495016327352871122917196026504758904760148391499245235850616838765611460630089577948665981247735905622903872682862860306107704253287284051312867625831877418240290183661755993649928399992531008191618616452091127799880839665225093055618092869662205901927957599941568
e2 = 84856171747859965508406237198459622554468224770252249975158471902036102010991476445962577679301719179079633469099994226630172251817358960347828156301869905575867853640850107406452911333646573296923235424617864473580743418995994067645338437540627399276292679100115018844287273293945121023787594592185295794983
C2 = 101960082023987498941061751761131381167414505957511290567652602520714324823481487410890478130601013005035303795327512367595187718926017321227779179404306882163521882309833982882201152721855538832465833869251505131262098978117904455226014402089126682222497271578420753565370375178303927777655414023662528363360
 
rat = int(n ** 0.5)
M = Matrix(ZZ, 3, 3)
M[0, 0] = e1
M[1, 0] = e2
M[2, 0] = n
M[0, 1] = rat
M[1, 2] = rat
 
L = []
for i in range(800, 2450):
    Target = vector([-int(n ** 0.66 * i / 1000) , int(n ** 0.16) * rat, int(n ** 0.16) * rat])
    M = M.LLL()
    GG = M.gram_schmidt()[0]
    TT = Babai_closest_vector(M, GG, Target)
    d1 = TT[1] // rat
    d2 = TT[2] // rat
    L.append(e1 * d1 + e2 * d2 - 1)
print(list(set(L))) ## this is c
 
for phi in c:
    d1 = inverse(e1, phi)
    print(long_to_bytes(pow(C1, d1, n)))
    d2 = inverse(e2, phi)
    print(long_to_bytes(pow(C2, d2, n)))
cs

  

crypto01


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
from sage.all import *
from flag import flag
from functools import reduce
 
def encrypt(m, e, n):
    n = int(n)
    size = n.bit_length() // 2
    m_low = m & ((1 << size) - 1)
    m_high = (m >> size)
 
    b = (m_low**2 - m_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
 
    return (EC((m_high, m_low)) * e).xy()
 
def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2
 
    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)
 
    return (m_high << size) | m_low
 
def gen_prime(size):
    p = random_prime(1 << size)
    while p % 3 != 2:
        p = random_prime(1 << size)
 
    q = random_prime(1 << size)
    while q % 3 != 2:
        q = random_prime(1 << size)
 
    if q > p:
        p, q = q, p
 
    return int(p), int(q)
 
 
 
SIZE = 512
HINTSIZE = 96
N = 3
 
flag = int.from_bytes(flag, "big")
assert flag < (1 << SIZE)
 
masks = [randint(1 << (SIZE-1), 1 << SIZE) for _ in range(N)]
masked_flag = reduce(lambda a, b: a ^ b, masks, flag)
 
 
count = 0
ciphertexts = []
while count < N:
    try:
        p, q = gen_prime(SIZE)
        n = p * q
 
        x = random_prime(int(n ** 0.40))
        y = random_prime(int(sqrt(2 * n // (144 * x*x))))
        zbound = -1 * int(round(((p-q) * (n ** 0.25) * y) / (3 * (p + q))))
 
        z_ = zbound + ((p + 1)*(q + 1)*y - zbound) % x
        e = ((p + 1) * (q + 1) * y - z_) // x
        d = inverse_mod(e, (p + 1)*(q + 1))
 
        assert (x*y*x*y < (2 * n // 144))
        assert (gcd(x, y) == 1)
 
        d = inverse_mod(e, (p+1)*(q+1))
        c = encrypt(masks[count], e, n)
        assert decrypt(c, d, n) == masks[count]
 
        ciphertexts.append({
            "n": n,
            "e": e,
            "c": c,
            "hint": p & ((1<<HINTSIZE)-1)
        })
        count += 1
    except KeyboardInterrupt:
        break
    except (ZeroDivisionError, OverflowError):
        pass
 
 
print("masked_flag = " ,masked_flag)
print("ciphertexts = ", ciphertexts)
 
cs


@diff (pcw) noted that the order of the elliptic curve must be $(p+1)(q+1)$ since $p \equiv q \equiv 2 \pmod{3}$.

This is a cool fact that I didn't know, but it could be easily guessed by the definition of $d$ in the script. 


So, first things first : is this really a elliptic curve challenge? The answer : probably not?

I thought this for a few reasons - I thought the generation of $e$ was quite convoluted so there should be a weakness.

The elliptic curve part looked too clean to have a vulnerability, and it's not even over a field. Hard to do anything, really. 


Therefore, I decided to take a look at how the parameter generation behaves.

First, I look at the sizes of the values. It 's clear that $y$ is small, so $zbound$ and $z$ are also quite small compared to $x$.

This leads to the following suspicion, is $e = \lfloor (p+1)(q+1)y / x \rfloor$? Generating parameters on our own, we see that this is true with a very high probability. This means that we can ignore $zbound$ and $z$ completely now! This is a good progress indeed :) 


This simplifies a lot of things, and we have a good, clean equation to work with. Start with $$ xe  = (p+1)(q+1)y - r \equiv (p+q+1)y - r\pmod{n}$$ with $r < x \approx n^{0.4}$. With $y \approx n^{0.1}$, we see that $(p+q+1)y - r \approx n^{0.6}$. So $x \approx n^{0.4}$ satisfies $xe \pmod{n} < \approx n^{0.6}$. 

Heuristically speaking, there should be a fairly small number of $x$ that satisfy that condition! Can we find them though?


Turns out the answer is yes. I guess you can do this with lattices, but here's a method I learned from competitive programming. 

In fact, given $L, R, M, A$, we can find the minimum nonnegative integer $x$ such that $L \le Ax \pmod{M} \le R$. 

The method is not long, but I don't want to type it all out, so here's a link (scroll down to the end of the editorial)

Also, a problem using this algorithm appeared in NWRRC, (problem G) set by tourist. 


Since we know $e, n$, we can select some $CUT \approx n^{0.6}$ and find the minimum $x$ such that $1 \le ex \pmod{n} \le CUT$. Of course, we have to be cautious with constants when selecting $CUT$. It's not too hard, since we can always verify our value of $x$ by checking its primality and size. This concludes the recovery of $x$, which is a huge progress again! Now we try to recover $y$. 


To recover $y$, we use basic inequalities. Note the following two inequalities $$ y = \frac{xe+r}{(p+1)(q+1)} \ge \frac{xe}{n + 3 \sqrt{n/2} + 1}$$ $$ y = \frac{xe+r}{(p+1)(q+1)} \le \frac{xe + x-1}{n + 2\sqrt{n} + 1}$$ which gives us decent lower/upper bounds. Turns out that this is also perfect, as the two bounds are actually equal! This recovers $y$. 


With this information, we can now bound $p+q$. Simply use $$ p+q = \frac{xe+r}{y} - 1 \ge \frac{xe}{y} - 1 $$ $$ p+q  = \frac{xe+r}{y} -1 \le \frac{xe+x-1}{y} - 1$$ which gives us a good bound for $p+q$. Now we proceed as we did in l33tcrypt in DownUnderCTF and use quadratic formula to get a good bound for $p$. Note that $p > q$. If we analyze the two bounds, we see that this gives us about 200 MSBs of $p$. Now we are practically done. 


We already know 96 LSBs of $p$ via the hint. This adds up to 296 bits of information, so we only need to determine 216 bits of $p$. This can be easily done with coppersmith method, i.e. Sage's small_roots. This part is very straightforward. Now we calculate $p, q, d$ and eventually the masks. The conversion of masks to the actual flag was done by @ironore15. This concludes the problem :D


Also, maybe you can recover $x, y$ with continued fractions on $e/n$? Maybe. I didn't try it :P

UPD : Okay I tried it and it works easily. Why didn't I think about this lmao... This is a much easier way to solve. :)

Basically, from $e = \lfloor (p+1)(q+1)y / x \rfloor$, we can guess that $$ \frac{e}{n} \approx \frac{e}{(p+1)(q+1)} \approx \frac{y}{x}$$ so $y/x$ is a good approximation of $e/n$. Find all convergents of $e/n$, and find those that have primes as its numerator and denominator. 

This gives us $x, y$, so we can proceed with the coppersmith attack as above. Much easier :)


UPD : The continued fraction solution is indeed the intended sol. I guess it could be proved using the given bounds :)

UPD : So apparently this thing had a name, KMOV cryptosystem. didn't know that :P



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
def kthp(n, k):
    if n == 0:
        return 0
    lef = 1
    rig = 2
    while rig ** k < n:
        rig = rig << 1
    while lef <= rig:
        mid = (lef + rig) // 2
        if mid ** k <= n:
            best = mid
            lef = mid + 1
        else:
            rig = mid - 1
    return best
 
def ceil(n, m):
    return (n + m - 1) // m
 
def optf(A, M, L, R):
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A = M - A
        L = M - L
        R = M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2
 
    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)
 
    return (m_high << size) | m_low
 
ciphertexts =  []
for C in ciphertexts:
    n = C['n']
    e = C['e']
    c = C['c']
    hint = C['hint']
    CUT = kthp( (int)(n ** 0.2) // 72, 2) * kthp(n, 2) * 8
    x = optf(e, n, 1, CUT)
    R = ((e * x + x - 1) // (n + 2 * kthp(n, 2) + 1))
    L = ((e * x) // (n + 3 * kthp(n//2, 2) + 1))
    y = (L + R) // 2
    assert L == R and x in Primes() and y in Primes()
    sum_L = (x * e) // y - 1 - n
    sum_R = (x * e + x - 1) // y - 1 - n
    lr = (sum_R + kthp(sum_R * sum_R - 4 * n, 2)) // 2
    sm = (sum_L + kthp(sum_L * sum_L - 4 * n, 2)) // 2
    assert sm <= lr
    assert (sm >> 312) == (lr >> 312)
    p_hint = hint
    K = Zmod(n)
    P.<t> = PolynomialRing(K, implementation='NTL')
    f = (p_hint * inverse_mod(2 ** 96, n)) % n + t + (2 ** (312-96)) * (lr >> 312)
    x0 = f.small_roots(X = (2 ** 220), beta = 0.5, epsilon = 0.03)
    ## print(x0)
    p = p_hint + x0[0] * (2 ** 96) + (2 ** 312) * (lr >> 312)
    p = (int)(p)
    q = n // p
    d = inverse_mod(e, (p+1) * (q+1))
    print(decrypt(c, d, n))
 
## thanks, ironore!
def recover_flag(masks, masked_flag):
    flag = reduce(lambda a, b: a ^ b, masks, masked_flag)
    return flag.to_bytes(512 // 8, 'big')
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def get_red(e, n):
    cur_num, cur_den = e, n
    num_1, den_1 = 0, 1
    num_2, den_2 = 1, 0
    while True:
        val = cur_num // cur_den
        nxt_num = cur_den
        nxt_den = cur_num - val * cur_den
        # calculate new convergent
        num_3 = val * num_2 + num_1
        den_3 = val * den_2 + den_1
        if isPrime(num_3) and isPrime(den_3):
            return num_3, den_3
        if den_3 > int(n ** 0.4):
            return -1
        # update convergents
        num_1, den_1 = num_2, den_2
        num_2, den_2 = num_3, den_3
        # update continued fractions
        cur_num, cur_den = nxt_num, nxt_den
 
ciphertexts =  []
for C in ciphertexts:
    n = C['n']
    e = C['e']
    c = C['c']
    hint = C['hint']
    y, x = get_red(e, n)
    R = ((e * x + x - 1) // (n + 2 * kthp(n, 2) + 1))
    L = ((e * x) // (n + 3 * kthp(n//2, 2) + 1))
    assert y == (L + R) // 2
    assert L == R and isPrime(x) and isPrime(y)
    ## continue as the initial solution
cs


저작자표시 (새창열림)

'CTF' 카테고리의 다른 글

PBCTF 2020 Crypto Writeups  (1) 2020.12.07
N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18
CryptoHack All Solve  (3) 2020.09.30
TokyoWesternCTF 2020 Crypto Write-Ups  (2) 2020.09.20
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19


오늘 남았던 2문제를 해결하여 올솔브를 했습니다. 2문제 다 쫄아서 못 건드리고 있었는데 펜 굴리니까 생각보다 무난하게 풀리네요 :) 

여기서 접근한 새로운 정보들이 많으니 공부 좀 해야겠습니다. 그래도 올솔하니까 후련하네요 ㅋㅋ 

저작자표시 (새창열림)

'CTF' 카테고리의 다른 글

N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18
SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
TokyoWesternCTF 2020 Crypto Write-Ups  (2) 2020.09.20
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19
InterKosenCTF 2020 Crypto 분야 Write-Ups (?)  (0) 2020.09.06

I participated in TWCTF 2020 as a member of the team D0G$. We got 1st place!


easy hash

I tried to do something but then @yoshiking sensei solved it. :D


sqrt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p
 
 
def encrypt(m, k, p):
    return pow(m, 1 << k, p)
 
 
assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)
 
k = 64
pt = bytes_to_long(flag.encode())
ct = encrypt(pt, k, p)
 
with open("output.txt", "w") as f:
    f.write(str(ct) + "\n")
    f.write(str(p) + "\n")
 
# 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
# 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
cs

So we are given $m^{2^{64}} \pmod{p}$ and $p$. We need to find $m$. The first thing we note is that $\nu_2 (p-1) = 30$. Therefore, we have $\text{gcd}(2^{64}, p-1) = 2^{30}$ possibilities for $m$, if we disregard the length and "TWCTF{" condition. This is a large number of solutions, but it's not impossible to brute force. We first find any solution of $m^{2^{64}} \equiv enc \pmod{p}$ by repeated usage of Tonelli-Shanks. Now, we may write all solutions as $m \cdot g^{(p-1)/2^{30} \cdot k}$, where $g$ is some generator easily found by Sage. We go over each solution, check if it's small enough to be a candidate first (optimization), then convert it to bytes and see if it meets the desired conditions. 

It was estimated to run in ~1.5 hours in my computer, so I asked for some computational help. 
@theoldmoon0602 and @ironore15 were kind enough to help me in this brute force.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
## Step 1 : Find any solution
def gogo(r, d, m):
    if d == 0:
        print(r)
        exit()
        return
    u = tonelli(m, r)
    if u == -1:
        return
    gogo(u, d-1, m)
    gogo((m-u)%m, d-1, m)
 
 
## Step 2 : Start Brute Force
res = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
ex = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271
assert pow(ex, 1 << 64 , p) == res
 
def is_ascii(s):
    return all(c < 128 for c in s)
 
gen = 3
jp = pow(3, (p-1) // (2 ** 30), p)
 
for i in tqdm(range(0, 2**30)):
    ex = (ex * jp) % p
    if ex.bit_length() <= 400:
        u = long_to_bytes(ex)
        if is_ascii(u) and b"TWCTF{" in u:
            print(u)
            exit()
cs
 
twin-d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
require 'json'
require 'openssl'
 
p = OpenSSL::BN::generate_prime(1024).to_i
q = OpenSSL::BN::generate_prime(1024).to_i
 
while true
    d = OpenSSL::BN::generate_prime(1024).to_i
    break if ((p - 1) * (q - 1)).gcd(d) == 1 && ((p - 1) * (q - 1)).gcd(d + 2) == 1
end
 
e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
e2 = OpenSSL::BN.new(d + 2).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
 
flag = File.read('flag.txt')
msg = OpenSSL::BN.new(flag.unpack1("H*").to_i(16))
n = OpenSSL::BN.new(p * q)
enc = msg.mod_exp(OpenSSL::BN.new(e1), n)
 
puts ({ n: (p*q).to_s, e1: e1.to_s, e2: e2.to_s, enc: enc.to_s }).to_json
cs

So we have $e_1, e_2$ corresponding to $d_1, d_2$, which have a difference of $2$.
Basically what this says is that $e_2^{-1} - e_1^{-1} \equiv 2 \pmod{\phi(n)}$. Therefore, we can simply write $e_1-e_2 \equiv 2e_1e_2 \pmod{n}$. 
This implies that $2e_1e_2 + e_2 - e_1$ is a multiple of $\phi(n)$. It is very well-known fact that given $n$ and a multiple of $\phi(n)$, we can factorize $n$. So apply that method to factorize $n$. The rest is basic RSA. Happy to get first solve :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
n = 26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433
e1 = 3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127
e2 = 20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905
enc = 18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046
 
cc = 2 * e1 * e2 + e2 - e1
 
tt = 0
cv = cc
while cv % 2 == 0:
    cv //= 2
    tt += 1
 
for i in range(3, 100):
    t = pow(i, cv, n)
    for j in range(0, tt):
        g = GCD(t-1, n)
        if g != 1 and g != n:
            print(g) ## this is p
            exit()
        t = (t * t) % n
 
p = 177276401739167429751099686272064967069179029118915820763787396008698833618702905602522557760805466539182350759150950532254737829482867347218636052172454990031666206911810532732619372311183056810552780771197878348351916381506465238562588760944922289622011858546760490648690942678177540128777265354408766804279
q = n // p
 
phi = (p-1) * (q-1)
d = inverse(e1, phi)
print(long_to_bytes(pow(enc, d, n)))
cs

The Melancholy of Alice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from Crypto.Util.number import getStrongPrime, getRandomRange
 
N = 1024
 
def generateKey():
    p = getStrongPrime(N)
    q = (p - 1) // 2
    x = getRandomRange(2, q)
    g = 2
    h = pow(g, x, p)
    pk = (p, q, g, h)
    sk = x
    return (pk, sk)
 
def encrypt(m, pk):
    (p, q, g, h) = pk
    r = getRandomRange(2, q)
    c1 = pow(g, r, p)
    c2 = m * pow(h, r, p) % p
    return (c1, c2)
 
def main():
    with open("flag.txt") as f:
        flag = f.read().strip()
 
    pk, sk = generateKey()
    with open("publickey.txt", "w") as f:
        f.write(f"p = {pk[0]}\n")
        f.write(f"q = {pk[1]}\n")
        f.write(f"g = {pk[2]}\n")
        f.write(f"h = {pk[3]}\n")
 
    with open("ciphertext.txt", "w") as f:
        for m in flag:
            c = encrypt(ord(m), pk)
            f.write(f"{c}\n")
 
 
if __name__ == "__main__":
    main()
 
cs

I had good fun solving this problem, so I'll write my thought process as well. 

This honestly looks like a perfect code, but the key line that left a question mark for me was line 35. 

$ord(m)$ is incredibly small, so maybe we can bypass the entire discrete logarithm?


To think further in this direction, we need some knowledge on $p-1$. I first checked if $q$ was prime - it was not.

Then I checked the factors of $q$ - I could brute force small primes, but I just went to FactorDB. Why not?

I found out that $3, 5, 19$ were factors of $q$, which was quite surprising to me.

I thought StrongPrimes generated a prime of a form $2 \cdot q + 1$ where $q$ is a prime. Oops?


Anyways, since $3 \cdot 5 \cdot 19$ was pretty large, so it seems this should be fine.

Discrete Logarithm calculation is hard, but calculation modulo a small prime is easy by Pohlig-Hellman style thinking.

Can we abuse this? Well, given the signature data we can calculate the logarithm of the $ord(m)$ modulo $3 \cdot 5 \cdot 19$.

So if we precompute all logarithms of 0 to 255 modulo $3 \cdot 5 \cdot 19$, we can find the "candidates" for each letter.


I did this, but found there are multiple solutions. I tried to fix this by working with $5710354319$, which is another prime divisor.

I thought this should also work using sage's BSGS and stuff, but it was way too slow.


I posted my partial result (candidates) on discord and asked for guesswork/recovery, then @yoshiking found the solution.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def crt(a, b):
    u, v = 0, 1
    for i in range(len(a)):
        u, v = CRT(u, v, a[i], b[i])
    return u
 
def get_DL(x, pr):
    gg = pow(x, (p-1) // pr, p)
    for i in range(0, pr):
        gt = pow(g, i * (p-1) // pr, p)
        if gt == gg:
            return i
 
def get_DLs(x):
    p_1 = get_DL(x, 3)
    p_2 = get_DL(x, 5)
    p_3 = get_DL(x, 19)
    return crt([p_1, p_2, p_3], [3, 5, 19])
 
cc = [-1]
for i in range(1, 255):
    cc.append(get_DLs(i))
 
xx = get_DLs(h)
 
res = []
fin = []
fom = ""
for x, y in res:
    s = ""
    u = get_DLs(x)
    v = get_DLs(y)
    ## v = xx * u + get_DLs(desire)
    res = (v - xx * u) % (3 * 5 * 19)
    for j in range(0, 255):
        if cc[j] == res and j <= 128:
            s += chr(j)
    print(s)
 
cs


XOR and shift encryptor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#!/usr/bin/python3
 
s = []
p = 0
 
def init():
  global s,p
  s = [i for i in range(0,64)]
  p = 0
  return
 
def randgen():
  global s,p
  a = 3
  b = 13
  c = 37
  s0 = s[p]
  p = (p + 1) & 63
  s1 = s[p]
  res = (s0 + s1) & ((1<<64)-1)
  s1 ^= (s1 << a) & ((1<<64)-1)
  s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c))  & ((1<<64)-1)
  return res
 
def jump(to):
 
  # Deleted...
 
  return
 
def check_jump():
  init()
  jump(10000)
  assert randgen() == 7239098760540678124
 
  init()
  jump(100000)
  assert randgen() == 17366362210940280642
 
  init()
  jump(1000000)
  assert randgen() == 13353821705405689004
 
  init()
  jump(10000000)
  assert randgen() == 1441702120537313559
 
  init()
  for a in range(31337):randgen()
  for a in range(1234567):randgen()
  buf = randgen()
  for a in range(7890123):randgen()
  buf2 = randgen()
  init()
  jump(31337+1234567)
  print (buf == randgen())  
  jump(7890123)
  print (buf2 == randgen())
 
check_jump()
 
init()
for a in range(31337):randgen()
 
flag = open("flag.txt").read()
assert len(flag) == 256
 
enc = b""
 
for x in range(len(flag)):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ])
  print ("%r" % enc)
 
open("enc.dat","wb").write(bytearray(enc))
 
 
cs


So basically what we have to do is efficiently "advance" the RNG large amount of times. 

The given RNG state transition can be regarded as a linear transformation over the $64^2$ bits in the state.

Therefore, we can model this by matrix multiplication, where the size of the matrix is $64^2$. 

Using binary exponentiation, we can get our random numbers relatively quickly.


I had thought of this but believed this would be way too slow, but @theoldmoon0602 wrote a beautiful code in sage and managed to find the flag. The code took about 30 minutes ~ 1 hour to run, according to the solver. 


The below code, by @theoldmoon0602, derives the key sequence. 

Also, for the write-up written by the actual solver @theoldmoon0602, check here.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
N = 64
F = GF(2)
 
def L(n):
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N - n):
    m[i + n][i] = 1
 
  return matrix(F, m)
 
def R(n):
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N - n):
    m[i][i + n] = 1
 
  return matrix(F, m)
 
 
def I():
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N):
    m[i][i] = 1
 
  return matrix(F, m)
 
def O():
  m = [[0 for x in range(N)] for y in range(N)]
  return matrix(F, m)
 
def genM():
  a = 3
  b = 13
  c = 37
 
  o = O()
  i = I()
  la = L(a)
  rb = R(b)
  rc = R(c)
 
  blocks = [
    [i + rc, i + la + rb + la*rb] + [o for _ in range(62)]
  ]
  for j in range(1, N):
    row = [o for _ in range(N)]
    row[(j+1) % N] = i
    blocks.append(row)
 
  M = block_matrix(F, [*zip(*blocks)])
 
  return M
 
def initial_state():
  s = "".join(["{:064b}".format(i) for i in range(N)])
  vec = []
  for c in s:
    vec.append(F(int(c)))
  return Matrix(F, vec)
 
def getvalue(row, index):
  v = 0
  for i in range(N):
    v = v*2 + int(row[0][index*N + i])
  return v
 
def dumpstate(a):
  xs = []
  for i in range(N):
    xs.append(getvalue(a, i))
  print(xs)
 
s = initial_state()
M = genM()
 
def init():
  global s, M
  s = initial_state()
  M = genM()
 
def randgen():
  global s, M
  res = (getvalue(s, 0) + getvalue(s, 1)) % ((1<<64)-1)
  s = s * M
  return res
 
def jump(n):
  global s,M
  s = s * (M^n)
 
init()
jump(31337)
for x in range(256):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  print(randgen() & 0xff) 
 
cs


circular

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
## keygen
 
require "openssl"
require "json"
 
p = OpenSSL::BN.generate_prime(1024)
q = OpenSSL::BN.generate_prime(1024)
k = OpenSSL::BN.generate_prime(2048, false)
n = p * q
File.write("pubkey.txt", { n: n.to_s, k: k.to_s }.to_json)
 
## interaction
 
require "functions_framework"
require "digest/sha2"
 
fail unless ENV["FLAG"]
 
key = JSON.parse(File.read("pubkey.txt"))
n = key["n"].to_i
k = key["k"].to_i
 
EXPECTED_MESSAGE = 'SUNSHINE RHYTHM'
 
FunctionsFramework.http("index") do |request|
  if request.request_method != "POST"
    return "Bad Request"
  end
 
  data = JSON.parse(request.body.read)
  cmd = data["cmd"]
  if cmd == "pubkey"
    return { pubkey: { n: n.to_s, k: k.to_s } }
  elsif cmd == "verify"
    x = data["x"].to_i
    y = data["y"].to_i
    msg = data["msg"].to_s
    hash = ""
    4.times do |i|
      hash += Digest::SHA512.hexdigest(msg + i.to_s)
    end
    hash = hash.to_i(16) % n
    signature = (x ** 2 + k * y ** 2) % n
 
    if signature == hash
      if msg == EXPECTED_MESSAGE
        return { result: ENV["FLAG"] }
      end
      return { result: "verify success" }
    else
      return { result: "verify failed" }
    end
  else
    return "invalid command"
  end
end
 
cs


Basically, we have to find $x, y$ such that $x^2 + ky^2 \equiv HASH \pmod{n}$. 

We know $k, HASH, n$, but not the factorization of $n$. This seemed to be very difficult. 


First few ideas of mine included the Brahmagupta's Identity and Pell's Equation. 

I tried to work on Pell's Equation + continued fractions, but it failed as well.


After a while, @ironore15 notified us that this scheme has a name - OSS signature.

I was quite surprised because I didn't think this would be an actual scheme in the literature.

Anyways, after a bit of googling I was able to find a paper that describes the attack.

The rest was relatively straightforward implementation. I was glad to see one of my ideas used in the attack.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def comb(x1, y1, x2, y2, k, n):
    return (x1 * x2 + k * y1 * y2) % n, (x1 * y2 - x2 * y1) % n
 
def solve(k, m, n): ## solve x^2 + ky^2 == m mod n
    print("solve", k, m, n)
    fu = kthp(m, 2)
    if fu * fu == m:
        return (fu, 0)
    if k < 0:
        se = kthp(-k, 2)
        if se * se == -k:
            retx = (m+1) * inverse(2, n) % n 
            rety = (m-1) * inverse(2 * se, n) % n
            return retx, rety
    if m == 1:
        return (1, 0)
    if m == k % n:
        return (0, 1)
    while True:
        u = random.getrandbits(1024)
        v = random.getrandbits(1024)
        m_0 = (m * (u * u + k * v * v)) % n
        if isPrime(m_0):
            if GCD(m_0, n) != 1:
                print("LOL", m_0)
                exit()
            x_0 = tonelli(m_0, (-k) % m_0)
            if (x_0 * x_0 + k) % m_0 == 0:
                break
    ms = [m_0]
    xs = [x_0]
    sz = 1
    while True:
        new_m = (xs[sz-1] * xs[sz-1] + k) // ms[sz-1]
        ms.append(new_m)
        if k > 0 and xs[sz-1] <= ms[sz] <= ms[sz-1]:
            sz = sz + 1
            break
        if k < 0 and abs(ms[sz]) <= kthp(abs(k), 2):
            sz = sz + 1
            break
        xs.append(min(xs[sz-1] % ms[sz], ms[sz] - (xs[sz-1] % ms[sz])))
        sz = sz + 1
    assert sz == len(ms)
    assert sz - 1 == len(xs)
    uu, vv = xs[0], 1
    dv = 1
    for i in range(1, sz-1):
        assert (xs[i] ** 2 + k) % n == (ms[i] * ms[i+1]) % n
        uu, vv = comb(uu, vv, xs[i], 1, k, n)
        dv = (dv * ms[i]) % n
    dv = (dv * ms[sz-1]) % n
    uu = (uu * inverse(dv, n)) % n 
    vv = (vv * inverse(dv, n)) % n
    X, Y = solve(-ms[sz-1], (-k) % n, n)
    soly = inverse(Y, n)
    solx = (X * soly) % n
    finx, finy = comb(solx, soly, uu, vv, k, n)
    godx = ((finx * u - k * finy * v) * inverse(u * u + k * v * v, n)) % n
    gody = ((finx * v + finy * u) * inverse(u * u + k * v * v, n)) % n
    return godx, gody
 
msg = 'SUNSHINE RHYTHM'
hsh = ''
 
for i in range(0, 4):
    cc = msg + chr(ord('0') + i)
    hsh += hashlib.sha512(cc.encode()).hexdigest()
 
request = {
    'cmd': 'pubkey'
}
X = web_request('POST', 'https://crypto02.chal.ctf.westerns.tokyo', request, False)
 
 
n = 25299128324054183472341067223932160732879350179758036557232544635970111090474692853470743347443422497121006796606102551210094872253782062717537548880909979729182337501587763866901367212812697076494080678616385493076865655574412317879297160790121009524506015912113098690685202868184636344610142590510988192306870694667596904330867479578103616304053889409982447653859514868824002960431331342963562137691362725961627846051021103954795862501700267818317148154520620016172888281127685503677751830350686839873220480306266506898497203511851305686566444690384065880667273398255172752236076702247451872387522388546088290187449
k = 31019613858513746556266176233462864650379070310554671955689986199007361221356361736128815989480106678809272137963430923820800280374078610631771089089882153619351592434728588050285853284795554255483472955286848474793299446184220594124878818081534965835159741218233013815338595300394855159744354636541274026478456851924371621879725248093305782590590080796638483359868136648681381332610536250576568502512250581068814961097404403694071264894656697723213779631364079010490113719021172301802643377777927176399460547584115127172190000090756708138720022664973312744713394243720961199400948876916817452969615149776530401604593 % n
goal = int(hsh, 16) % n 
 
x, y = solve(k, goal, n)
print((x * x + k * y *y - goal) % n)
 
request = {
    'cmd': 'verify',
    'x': str(x),
    'y': str(y),
    'msg': msg
}
 
X = web_request('POST', 'https://crypto02.chal.ctf.westerns.tokyo', request, False)
print(X)
cs


저작자표시 (새창열림)

'CTF' 카테고리의 다른 글

SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
CryptoHack All Solve  (3) 2020.09.30
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19
InterKosenCTF 2020 Crypto 분야 Write-Ups (?)  (0) 2020.09.06
Crypto CTF 2020  (2) 2020.08.16

티스토리툴바