[Dreamhack][CryptoPS] Chinese what?

1.문제 분석

• 중국인의 나머지 정리를 활용하는 문제
• 확장된 유클리드 알고리즘을 활용하는 문제 (modular inverse)

---

2. 기본 아이디어

1. 주어진 p1, p2, p3, c1, c2, c3를 통해 수식을 계산해준다.
2. M, M에 따른 m1, m2, m3, 각각의 역원을 계산해준다.

---

3.문제 풀이

 

먼저 문제에서는 다음과 같은 값이 주어진다.

 

output

 

prob.py

 

느낌상으로도 나중에 c1, c2, c3를 병합하면 flag가 나올 것 같다.

 

중국인의 나머지 정리는 간단하게 다음과 같다.

 

CRT

 

연립 합동식 문제고 자세한 것은 구글링하면 금방 찾을 수 있다.

 

이제 코드를 짜보면

 

 

code

 

이 문제의 경우 p값들이 굉장히 큰 값이므로 모듈러 역원을 구하기 위해서는

 

확장된 유클리드 알고리즘을 사용할 필요가 있다.

 

그것을 구현한 것이 바로 mod_inv이며

 

소수들의 곱 M을 구한 후

 

각각의 m값들을 구해

 

모듈러 역원을 구해준 후

 

 처음상태로 복원시켜주면 된다.