점근 표기법: 알고리즘의 시간/공간 복잡도를 입력 데이터 크기 N에 대해 표기하는 방법아주 큰 N에 대해 고려 (N->무한)가장 영향을 많이 주는 것만 고려예) x^2+100x -> x^2상수나 계수는 무시5x -> x종류Big-O (가장 최악의 경우): 가장 많이 쓰는 표기법Big-Ω (가장 최고의 경우)Big-Θ: (Big-O == Big-Ω)수학적 정의Big-O임의의 함수 f(n)에 대해 양의 상수 c와 n0에 대해f(n)=n0) 이런 c, n0이 존재한다면이때 f(n)은 O(g(n))의 복잡도를 가진다.-> 즉, 일정 수준 이상에서 항상 f(n)보다 더 큰 g(n)을 찾는 것!예) f(n) = 3n^2+n+100일때, 4n^2만 되어도 n0= 10.6 근처 이후로 4n^2이 계속 크다.따라서 g(..

비대화형 ZKP: 지식 증명할 때 상호작용 없음 (증거(x1, x2)를 딱 한번만 전송)과정메세지가 m^e = c (mod N)로 암호화 됨. (e, c, N은 공개됨) 이때 m을 공개하지 않고 m을 알고 있다는 걸 증명이후 검증자가 계산할 때 x1*x2 = c (mod N) 라면 검증 성공(공개/전송된 파라미터에서 에서 m을 알아내긴 어려워 증명자는 m을 밝히지 않고 m을 알고있다 증명 가능!)임의의 정수 r1을 선택(공개x), 이후r2 = m * r1^(-1) (mod N)x1 = r1^e (mod N)x2 = r2^e (mod N)에서 계산된 (x1, x2)를 전송이후 검증자가 계산할 때 x1\*x2 = c (mod N) 라면 검증 성공(공개/전송된 파라미터에서 에서 m을 알아내긴 어려워 증명자는 ..

영지식 증명: 상대에게 구체적인 내용은 알리지 않은 채 어떤 주장을 참이라는 걸 증명하는 방법완전성: 주장이 참이라면 항상 증명을 받아들일 수 있다건실성: 주장이 거짓이라면 증명자가 검증자를 속일 확률이 매우 낮다영지식성: 검증자는 주장이 참이라는 사실만 알 수 있지 그 외의 정보는 모른다대화형 ZKP: 지식을 증명할 때 상호작용 있음 (증거를 여러번 전송)과정p는 매우 큰 소수, g는 Zp의 생성자B = g^a (mod p)로공개 피라미터 (p, g, B)를 합의한다증명자는 w = (k - a*r) (mod p-1)을 통해 w를 계산하고 전달한다.만약 V = g^w * B^r (mod p)가 만족한다면 검증 성공이 과정을 여러번 반복해 증명자가 a를 알고 있을 확률을 높인다.증명자는 임의의 정수 k (..

ElGamal 서명: D-H 알고리즘의 발전형디피-헬만 알고리즘에서 사용했던 (g, p, y)를 사용하면서 서명기능까지 있다!과정큰 소수 p와, g, 비밀키 x선택 (단, 1y = g^x (mod p) 계산공개키: (p, g, y), 개인키: x이후 서명 검증y^r*r^s (mod p)= g^M' (mod p)라면 유효함서명(r, s)해싱: M -> M'랜덤값 k를 선택 (단 1 r = g^k (mod p)s = k^(-1)(M' - xr) (mod p-1) (단, k^(-1)은 mod p-1에서 곱셈 역원)예앨리스가 밥에게 서명과 메세지를 보낸다고 한다. 파라미터는 g = 7, p = 11을 합의해놨다. (편의를 위해 작은 소수로 정함.)앨리스의 개인키 = 3, 밥의 개인키 = 4앨리스의 공개키 = 7..

디지털 서명: 메세지는 서로만, 그러나 증명은 아무나 할 수 있게역할송신자의 신원 증명메세지가 중간에 조작되지 않았단 증명메세지를 자신이 보냈다는 걸 부인하지 않게 하는 증명RSA 서명이전에 RSA를 사용할 땐 앨리스만 개인키를 정했으나, 디지털 서명에서는 송신자인 밥도 소수 2개를 고르고 공개키, 개인키를 생성한다.이후 밥은 보낼 메세지를 해시로 바꾸고 공개한다.공개된 메세지 해시에 개인키로 서명을 한다.밥의 공개키로 서명을 복호화하고, 만약 이것이 메세지 해시와 같다면 이 메세지는 밥이 보낸거라 할 수 있다.예)암호학 둘러보기 9 참고공개 파라미터(7), 보내는 메세지(8) 등 이전 RSA와 동등한 조건이라 가정할 떄,이전과 같이 밥은 앨리스의 공개키(N)으로 암호화: C = 8^7 (mod 15) ..

정수론 과제 중...문제: 1. 방정식 ax+by+cz = 1이 정수해를 가지는 조건은 무엇인가?         2. 해가 존재한다면 일반해를 찾는 방법은 무엇인가?         3. 예시로 155x+341y+385z=1의 정수해를 찾아라 1. 방정식 ax+by+cz = 1이 정수해를 가지는 조건은 무엇인가?a, b, c의 순서는 고려하지 않아도 된다.추측: gcd(a, b, c) = 1 이라면 ax+by+cz = 1이 정수해를 가진다.by 선형방정식 정리,    ax+by=gcd(a, b)를 만족하는 해인(x1, y1) (단, x1, y1은 정수)를 구할 수 있다    따라서 정수 p에 대해 p(ax+by) = pgcd(a, b)를 통해 gcd의 p배를 만드는 해도 찾을 수 있다.따라서 ax+by+c..

Lena 11 이번에도 register 문제다.프로그램 아이디에 맞는 패스워드를 입력해야 select 기능을 쓸 수 있다. 따라서 리버싱으로 패스워드를 알아내야 한다. 문자열 검색으로 register 검사하는 곳을 찾았다.WritePrivateProfileStringA로 입력한 문자열을 특정 섹션에 저장하고 GetPrivateProfileStringA로 섹션에 저장된 문자 버퍼를 가져올 수 있다는 것을 알았다.https://learn.microsoft.com/ko-kr/windows/win32/api/winbase/nf-winbase-writeprivateprofilestringahttps://learn.microsoft.com/ko-kr/windows/win32/api/winbase/nf-winbase..

Lena 9 이번엔 key를 찾는 문제다. 설치 관리자를 보면 검증하는 부분이 아무것도 없다. 이것도 지난번 Lena 8과 마찬가지로 설치한 파일에서 검사가 이루어진다.설치하고 실행하자마자 구매창이 뜬다. 이름이나 회사같은 정보 입력 없이 register key를 입력한다고 뜬다.예전에 abexcrackme에서 많이 봤던 vba가 보인다. vba에서 많이 쓰였던 것은 다음과 같다. __vbaVarTst: 모든 데이터 타입 비교__vbaStrCmp: 문자열 데이터 비교 일단 vbaVarTstEq밑을 계속 따라가며 register key가 있는지 찾아본다.대표사진 삭제사진 설명을 입력하세요.뭔가 수상한 문자열이 보인다. 수상한 문자열 oeiu-564-oqei-97을 입력하면 register 된다.

Lena 7 이번에도 어김없이 unregistered version이다.온라인 구매 페이지는 이미 사라진 지 오래라서 register에서 이메일과 라이센스를 검사하는 부분을 뛰어넘을 수밖에 없다. email로 문자열 검색을 하면 수상한 부분이 나온다.  함수들을 보면 MrBills.004A40B6는 큰 영향은 없어보이고,MrBills.0040714C에서 직접 검사가 이루어져 반환값이 0이라면 register한다. 따라서 프로그램 실행 중간에 중단점을 걸고 EAX를 바꾸거나 조건문을 JNZ에서 NOP로 바꾸면 된다. 그러면 register했다고 뜬다. 참고로 프로그램을 이전에 푼 문제와 다르게 종료할 때마다 unregistered로 바뀌므로 NOP로 아예 패치한 것이 나아 보인다.

Lena가 만들어진지 오래되었다 보니 일부 문제는 실행이 잘 안되네요ㅠㅠLena 5는 나중에 풀겠습니다. Lena 6 이번에는 앱이 창을 하나 띄우고 작동하지 않는다.근데 이건 내 윈도우와 프로그램 간 호환성의 문제였다.따라서 XP로 호환성을 변경해서 열어 실행했다.또한 ollydbg에서 예외처리를 무시하게 해 중간에 멈추지 않고 실행하게 했다.이번에도 실행하자마자 unregistered version이라고 뜬다.또한 5일동안 밖에 못 쓰게 되어있다.여기저기 눌러보다 보니 reg key를 사용해 register할 수 있다는 것을 알 수 있었다. 문자열 찾기로 register key를 검사하는 곳을 찾을 수 있다.위에서 올바른 버전에 엑세스 하는지 검사하고, 올바른 버전이라면 key를 검사하고 regist..