대충공부한거적어두는블로그

이렇다고 한다.. 최대한 직관적으로 구현하고자 했다 (물론 더 간단한 방법도 있겠지만) 계수 (a,b,c,d) 간 관계식을 이용해서 코드를 짜면 될 것 같다 def extended_euclidean(X,Y): if X0: q = x//y r = x%y if r==0: break # GCD 구해짐 x,y,a,b,c,d = y,r,c,d,a-q*c,b-q*d return c,d,y x,y = map(int, input().split()) a,b,GCD = extended_euclidean(x, y) print(f'{a} * {x} + {b} * {y} = {GCD}') 물론 파이썬 라이브러리를 사용해서 개 ez하게 구할 수도 있다 from gmpy2 import gcdext gcd, s, t = gcdext..

RSA 암호화 알고리즘이란 - modular exponentiation operation 기반으로 한 암호화 알고리즘 - n과 e를 공개키로, d를 개인키로 사용하여 아래와 같이 exponentiation을 통해 암호화 및 복호화 한다 - key generaton 방식은 아래와 같다 // 먼저 적절한 소수 p와 q를 선택하여 n을 구한다 // e를 적절히 선택하고, 개인키 d를 역산한다 // 만약 attacker가 p, q, d 중 하나를 찾는다면 모든 ciphertext에 대해 decrypt가 가능할 것이다 취약점 분석 예제 1 from sympy import randprime, nextprime from secret import pt p = randprime(pow(2, 511), pow(2, 512..

RC4 알고리즘이란? - 암호화와 복호화에 동일한 shared key를 사용하는 symmetric encryption - 스트림 암호 중 하나로 전송 계층 보안(TLS, SSL) 등 여러 프로토콜에 사용되었던 암호 방식 - 256바이트 이내의 key와 256바이트 초기배열 S를 이용해 PlainText와 동일한 길이의 Key Stream을 생성하고, 각 바이트 XOR을 통해 key stream을 생성한다 - key stream을 안다면 xor을 통해 암호화 및 복호화가 가능하다 RC4 알고리즘 동작 방식 Step1. 초기 상태 벡터 S와 임의 벡터 T를 생성한다 - S와 T는 256바이트 벡터 - S[i]=i (i=0~255) 인덱스 값을 채우고, T에는 key를 반복적으로 채운다 Step2. KSA 알..

AES 암호화 알고리즘 - Advanced Encryption Standard, 블록 암호 - Block Size: 16 Bytes - Key size: 16 Bytes(AES128) / 24 Bytes(AES192) / 32 Bytes(AESE256) - plaintext 길이가 16*k보다 작을 때 padding을 붙인다 * 주로 PKCS#7 표준을 사용함 (padding 6개 필요하면 b'\x06'으로 채우고, 2개 필요하면 b'\x02'로 채우는) * plaintext 길이가 16의 배수이면 padding b'\x10'*16 을 뒤에 붙인다 - plaintext의 길이가 block size보다 클 때 어떻게? => mode of operation * ECB(Electronic CodeBook) m..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

- 두 수의 GCD를 구해주는 GCD 함수를 정의하고 int GCD(int x, int y) { while(true) { if(x>y) { x = x%y; if(x==0) return y; } else { y = y%x; if(y==0) return x; } } } - 연속한 데이터끼리 GCD를 구한다, 반복적으로 적용하기 위해 cyclic하게 동작할 수 있는 Queue 자료형 활용 - Queue에 데이터가 한 개 남는다면 그것이 GCD 일 것. (최적화: GCD 리턴값 1이면 바로 break) queue q; // data int x1, x2, gcd; while(true) { x1 = q.front(); q.pop(); if(q.empty()) { gcd = x1; break; } x2 = q.fro..

user input 숫자인지 문자인지 - stoi(), stol(), stod() 등의 함수 에러처리로 파악한다 bool check_number(string s) { try { stoi(s); } catch (const invalid_argument& e) { // 숫자 형태 아닐 때 return false; } catch (const out_of_range& e) { // 표현 가능 범위 넘었을 때 return false; } return true; } in python? - unsigned 정수에 한해 isdigit() 함수를 사용 가능하다 ("123"은 true, "25kim6"은 false) for _ in range(m): tmp = input() if tmp.isdigit(): print(l[..

main에 최적화를 위한 두 줄 추가하고 시작하면 시간 초과 잘 안 난다 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); } 벡터 내에 특정 element 있는지 이진 탐색으로 확인하는 방법 - lower_bound를 사용해 삽입될 위치 포인터를 리턴받은다음 v.end() 아니고 해당 주소에 element 있는지 확인하면됨 sort(v.begin(), v.end()); for(int i=0; i> s; vector::iterator it = lower_bound(v.begin(), v.end(), s); if(it != v.end() && *it == s) cnt++; } python bisect...

보호되어 있는 글입니다.