본문 바로가기

전체 글

(78)
[*CTF Writeup] Crypto - MyEnc 문제 설명 from Crypto.Util.number import getPrime,bytes_to_long import time,urandom from flag import flag iv=bytes_to_long(urandom(256)) assert len(flag)==15 keystream=bin(int(flag.encode('hex'),16))[2:].rjust(8*len(flag),'0') p=getPrime(1024) q=getPrime(1024) n=p*q print "n:",n cnt=0 while True: try: print 'give me a number:' m=int(raw_input()) except: break ct=iv for i in r..
[*CTF Writeup] Crypto - GuessKey2 문제 설명 from random import randint import os from flag import flag N=64 key=randint(0,2**N) # print key key=bin(key)[2:].rjust(N,'0') count=0 while True: p=0 q=0 new_key='' zeros=[0] for j in range(len(key)): if key[j]=='0': zeros.append(j) p=zeros[randint(0,len(zeros))-1] q=zeros[randint(0,len(zeros))-1] try: mask=int(raw_input("mask:")) except: exit(0) mask=bin(mask)[2:] ..
[Crypto] 디피 헬만 (Diffie-Hellman) 알고리즘과 취약점 Intro 디피 헬만(Diffie-Hellman) 키 교환은 이산 로그(Discrete Log) 문제의 어려움에 기반한 키 교환 방식이다. 이 글에서는 디피 헬만 키 교환의 동작 원리와, 그리고 동작 과정에서 잘못 구현될 수 있는 부분들의 후보를 간략하게 나열함으로서 디피 헬만 알고리즘의 취약점을 공격하려는 초보 크립토그래퍼에게 도움을 주려고 한다. 작동 과정과 원리 디피 헬만 키 교환은 공개된 통신 위에서, 두 사람이 다른 사람은 알지 못하고 둘만이 아는 공유된 정보(Shared Secret)을 갖도록 하는 방법이다. 이 알고리즘을 이해하기 위해서는 간단한 대수적 지식이 필요하다. 기본적으로 덧셈과 곱셈이 정의되었을 때 모듈러 $n$에 대한 수의 집합 $0, 1, 2, \dots , n-1$은 환(Ri..
USACO 2020 Open contest Gold 풀이 Intro PS를 거의 한달간 접었었는데, 올해 ICPC를 나갈 수 있다는 희망이 보여서 급하게 PS 재활 중입니다. 최대한 빨리 플래티넘을 안정적으로 해결할 수 있는 실력까지 올렸으면 좋겠네요. 가능할지는 아직 미지수입니다. 이 셋 푸는데도 두시간은 넘게 걸렸으니 미래가 어둡네요 :( 18874 Haircut 문제 링크 : https://www.acmicpc.net/problem/18874 문제를 요약하면 각 $j$에 대해 $j$보다 큰 수열의 원소들이 정확히 $j$로 바뀔 때, 수열의 inversion을 구하는 문제입니다. 이런 문제에서 흔히 나오듯이 $j$를 큰 수부터 작은 수까지 움직이면서 차례대로 구해봅시다. 수열의 inversion은 수열의 각 원소 $a_i$에 대해 인덱스가 $i$보다 작으면..
(임시) 2020 ICPC Seoul Regional 후기 * 페이스북에 올린 것을 급하게 그대로 올립니다. 14일날 있었던 Seoul Regional과, 그리고 리저널을 치기 위해서 노력했던 시간들에 대해 짧은 후기글을 올립니다. (긴 후기는 나중에 블로그에 올라올 것 같습니다.) 두서가 좀 없어도 이해해 주세요. 저희 팀은 결성된 지 상당히 오래 된 팀입니다. 올해 1월에 만들어졌고, 그때부터 팀연습을 몇 번 했던 것 보면 태생이 빡겜을 하기 위해 만들어진 팀이었던 것 같습니다. 저 또한 재수하려고 마음을 먹었다가 이 팀 구성이면 Semi-World Final에는 무조건 진출하겠다고 생각이 들어서 재수를 포기하고 PS를 계속 했습니다. 결과적으로 좋은 성적을 냈으니 옳은 선택이었다고 생각합니다. 사실 저희 팀이 객관적으로 잘하는 팀이다 말하기는 아직도 힘들다..
Random Problem Solving 1 Intro 정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다. 20045 Trading System 먼저 다음과 같은 값을 찾는다. 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$ 이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다. 이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다..
[BOJ] 17524 Dryer 문제 링크 : www.acmicpc.net/problem/17524 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다. 그 다음으로 해야 하는 관찰들은 다음과 같다. 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다. 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다. $k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대..
[SCPC] 2020 1차 예선 풀이 Intro대충 4시간 정도 때려 박아서 1~4번에서 만점을 받았고, 5번은 문제만 읽었습니다. 예전 SCPC 기출에 비해서는 확실히 난이도가 균일해진 것 같습니다(https://newdeal123.tistory.com/61 참조 요망). 제가 예상하는 Solved.ac 티어 난이도는 다음과 같습니다.다이어트 (Silver 3)카드 게임 (Platinum 3)사다리 게임 (Platinum 3)범위 안의 숫자 (Platinum 2)우범 지역 (Diamond 2~3?)1. 다이어트다음과 같이 생각해봅시다. 일단 자명히 두 식단에서 칼로리가 낮은 순으로 K개만 먹어야 한다는 것을 알 수 있습니다. 이때 식단 A의 가장 큰 칼로리를 가지는 식사는 B의 어떤 식사랑 매칭시켜야 할까요? 당연히 B의 가장 작은 칼로리..