Yubin Choi

5. ECC. 어렵다. 타원곡선 이름만 들어도 무섭게 생기지 않았는가. 일단 체크해볼 사항은 이렇다.
1) EC가 정의된 field는 어떤가? IntModRing이라면 modulus 는 소수인가? 소수의 거듭제곱인가? 합성수인가?
2) y=0의 근은 어떤 꼴인가?
3) Sagemath에서 construction 했을 때 에러가 나는가? (ex singular EC, abnormal generator)
4) addition 등의 연산이 제대로 주어져있는가?
위에거들 고민해보고 답이 안나오면 구글링 열심히 하자.

PRNG에 관한 얘기로 조금 확장시켜보자면, MT19937 같은것도 자주 나오는데, 이건 파이썬 라이브러리 있다고 거기에만 의존하면 좀 피본다. truncate 시켜서 주거나 full bit information을 안주는 경우들도 있어서, 빨리빨리 대응하려면 MT19937 정도는 어떤 식으로 동작하는지 기억해두면 좋다. PRNG 유형을 나눠보자면
1. LFSR
2. XORSHIFT
3. LCG
뭐 이런것들이 있다. 외의 것들도 많으므로 문제 많이 풀어봐야함...

4. LFSR
얘는 쉬운건 진짜 쉽고 어려운건 진짜 어려운것 같다. 쉬운 문제는 그냥 간단한 브포에 점화식 붙여서 식세우고 슥슥하면 된다.
어려운 문제는, 내기준으론, 비트 일부가 truncate 되어 있다던가 하는 문제들. 이건 격자 써야 한다. or SMT solver 잘 깎으면 나옴. 솔직히 SMT solver 쓰는건 내가 잘 안해봐서 뭐라 얘기 못하겠다.

3-2. 커스텀해시
문제에서 뭔 이상한 해시를 직접 만들었답시고 보여주면 높은 확률로 그게 문제임. 이 경우에는 보통 해시 구성하는 큰 틀을 따를 확률이 높은데, 머클댐가드, 스펀지 요정도 우선 확인해보면 좋음. 만약 머클댐가드라면 머클댐가드에서 통하는 공격 몇개 시도해보고. 만약에 그런 틀에서 발생하는 문제가 아닌거같으면, 뭐 두 평문 xor하면 어떻게 되는지, nullbyte concat하면 어떻게 되는지 등등 알잘딱 해야함.

3-1. 취약한 상용해시(i.e. md5)
얜 진짜 별에별게 다 됨. 가정용 pc로도 짧은 시간 안에 충돌쌍 수만개 찾을 수 있음. 머클댐가드라 충돌쌍 하나 찾으면 충돌쌍 무한히도 만들 수 있음. length extension 같은것도 비슷한 이유에서 발생함. 깃헙에 잘 찾아보면 md5 checksum이 동일한 다른 확장자의 파일 만들기 뭐 이런것도 있는데 문제마다 보고 필요한거 갖다 쓰면 됨.

3. 해시
해시 문제 풀려면 해시가 어떻게 구성되는지에 대해서는 간략하게라도 알아야함. 머클댐가드, 스펀지 이런 구조가 있다는건 항상 인지하고 있어야 하고, 그 구조가 정확히 어떻게 되는진 문제 풀때 찾아보면 된다.

얘도 뭐 다른 도메인에 대해서도 나오는데, 뭐 행렬 같은건 진짜 흔하게 생각해볼 수 있는 듯. 어느 카테고리에서도 마찬가지인데, 행렬에 관해서 곱셈에 관한 뭔가가 나오면 대각화, jordan form, eigenvalue 이런거 생각해봐야함.

2. DH protocol - 얘도 정의는 well-known. RSA만큼 자주 나오지는 않음.
그다지 생각나는게 많지 않음. 주로 도청자 eve의 입장에서 플레이하도록 출제됨. 우선은 생각해봐야할 게
1) 파라미터를 내가 설정할 수 있는가?
2) 만약 그렇다면 파라미터의 검증은 어떻게 이루어지는가?
3) 내가 참여/도청할 수 있는 통신은 몇번인가?
4) 파라미터는 재사용되는가?
이런걸 고려하면서 정수론적으로 잘 풀어봐야함. 인터넷 상에 뭐 DH-Backdoor construction에 관한 자료가 좀 있던거 같기도 하고.

위에서 설명한 두 가지 경우가 대다수이나, 기괴한 카테고리인 만큼 기괴한 변형들도 몇 있다.
1-3. 다른 도메인에서의 RSA.
얘는 정말 순수한 수학퍼즐이라 할 수 있겠다. 도메인의 특성에 따라 할 수 있는게 정말 다양하게 나뉘기 때문이다. 예를 들자면 행렬로 하는 RSA 같은거. 주요하게 살펴볼 요소는
1) 도메인의 multiplicative order가 알려져 있는가
2) qth root가 쉽게 계산될 수 있는가
3) finite field 상으로 환원될 수 있는가
페이퍼에서 그 결론을 찾을 수 있는 경우도 많다.

격자같은 경우에는 linear한 식이 있을 때 격자를 만들고 SVP의 근사해가 LLL로 구해질 수 있음을 이해한 걸 전제로 한다. 격자는 깎는법도 배워야하고 하니 이 세미나에서 다루기엔 다소 버거운 주제.

1-2. N을 소인수 분해하지 않고 평문을 복구
이 케이스는 그다지 흔한 케이스는 아니다. 가장 유명한 예시는, 동일한 N과 평문에 대해 서로소인 두 공개지수 e1, e2를 사용하는 예시이다. 만일 그러하다면, e1*x+e1*y=1 인 두 정수 x,y가 존재하고, c1^x*c2^y는 m과 합동이므로, N의 소인수분해 없이 m을 복구할 수 있다.
혹은, 평문에 관한 낮은 차수의 다항식이 보장되며 평문이 충분히 작은 수인 경우에는 coppersmith method로 해결될 수 있다. 또다른 예시로는 격자가 있으나 어려우니 생략.

gcd를 이용하는 방법은 쉬우면서도 뉴비에게 다소 낯선 테크닉인데, 보통의 풀이 flow는 다음과 같다.
1. 어떤 수를 계산할 수 있다.
2. 그 어떤 수가 mod p에서 0과 합동이다.
3. => gcd(어떤 수,N) > 0 이며, 높은 확률로 < N이다.
이 경우, gcd가 p 그 자체일 확률이 높다.

N을 소인수분해하는 경우가 기술적으로 상당히 까다롭다. 별 이상한 정수론적인 지식을 들고 와서 괴롭게 한다. 쉽고 잘 알려진 페르마소인수분해부터 시작하여, cyclotomic polynomial 같은 어려운 개념들이나, 각종 페이퍼를 들고 오는 문제들도 꽤나 자주 보인다. 간단한 테크닉을 몇개 얘기해보자면,
- 페르마 소인수분해
- ct와 N의 gcd 이용하기
- 소인수의 특수꼴 이용하여 식정리하기

1-1. 이 경우, 대부분 N의 소인수인 p 혹은 비밀키인 d를 구하는 문제가 출제된다. 이에 해당하는 기법은 꽤나 많이 다양한데, d를 구하는 문제는 심하게 창의적인 경우는 보지 못한 듯 하다. 일반적으로 wiener's attack 등의 것이 자주 출제된다. Cryptohack에 이와 관련한 문제가 몇 있으니 참고. (예시는 추후에 찾아서 추가해놔야겠다)

우선 엔트리포인트를 잡아야한다. RSA는 pt를 잘 구하는게 목적인데, 여기서 우선 두가지 유형으로 나뉜다.
1-1. 비밀키를 찾아 m을 복호화한다.
1-2. 비밀키를 찾지 않고 m을 복호화한다.

1. RSA - 정의는 well-known. 그치만 정의가 잘 알려진 놈이 ctf에 그득그득 나온다는건 그만큼 기괴한 변형이 많다는거다.

동아리 세미나 준비 차원에서 쓰는 ctf crypto 얘기

With some simple calculations, we get (-f(x))e^(-f(x))=-x, and this implies that g(x)=-f(-x) satisfies g(x)e^g(x)=x thus g(x)=W(x). Therefore the g.f. of the number of labeled rooted trees with n vertices is -W(-x).

A representative example is the number of labeled rooted trees with n vertices. For its gf f(x), we can find that e^f(x) is the gf to choose children of the root. Then, f(x)=xe^f(x) is trivial since we can construct a tree by selecting the root and choose its children.

Lambert W function(which is defined as a function satisfies x=W(x)e^W(x)) seems not related to combinatorial approaches, but actually does.

why is he so obsessed with X

maybe some drafts or ideas for blog posts?

Actually the first one is epsilon-delta argument of the second one

Many articles usually introduce Big-Oh notation in two ways
f(n)=O(g(n)) if and only if
1. f(n)<cg(n) for a big enough positive integer n and some positive constant c
2. lim n->infinity f(n)/g(n) < infinity
but it was so hard thing for me as a child to realize those two are equivalent

What should I post here?

Hello world!