티스토리 뷰
문자를 숫자로 바꾸기
A=0 B=1 이런식으로 , 근데 5를 넘어가는수를 쓸수가 없으니 5진법으로 계산함
BED = 143(5)이므로 1X25 + 4X5 + 3X1 = 48 로 계산한다
48을 5진법으로 바꾸려면? = 9X5+3 = (1X5+4)X5+3 = 1X5^2 + 4X5 + 3 = 143(5) 로 하여 BED란 글이 나온다.
95 = 340(5) = DEA
알파벳 뿐만 아니라 특수문자들도 필요함
아스키코드를 사용 , 0부터 255까지 수를 이용
Ord() 함수는 해당하는 아스키코드 값을 알려준다.
Ex) Chr(65) = 'A' ord('A') = 65
비밀나누기
비밀메시지 : M =777
두개의 비밀 조각으로 나누기
R=111 M-r = 666
임의의 정수를 고를때 모든 정수가 선택될 화귤이 똑같을 수가 없음=> 무한
먼저 정수 n을 가능한 모든 비밀메시지보다 큰값으로 잡고 비밀 M이나 비밀조각 r,
M-r을 n으로 나눈 나머지로 봄
=> 왜 큰값으로 잡아야되나? 4자리 비밀이라고 할때 1000으로 나누면 9999와 8999의 나머지가 동일하여 머가 비밀메시지 인지 알수가 없음.
여러개의 조각으로 나누고 싶으면 어떻게 할까?
=> 4명이면 3명에게 임의의 숫자를 주고 나머지 한명에게 빼고 남은거를 준다.
N(sqrt(2))
N(pi,digits=100) = > 100자리까지 pi값을 알고싶다.
Tan? 라고 하면 해당 명령어를 알수있다.
Range(3) => 0 1 2 range(1,3) = 1 2
Mod(7,3) = > 7을 3으로 나눈 나머지
여기서 Mod(7,3) %5 하면 에러가 난다.
보물지도의 조각 중 미리 정한 개수보다 많이 모으기만 하면 완성할 수 있음
=> 샤미르의 쓰레스 홀드
Lagrange 보간다항식
-> 평면에서 두 점을 지나는 직선은 항상 존재하고 유일
-> 세점의 경우 : 2차 혹은 이하 함수
-> t개의 점의 경우 t-1차(혹은 이하) 다항함수가 항상 존재하고 또한 유일함
S.expand()하면 식이 예쁘게 나열됨
시프트 암호
A-> B, B-> C (한자리씩 민다)
HELLO => IFMMP
A->C B->D ..(두자리씩 민다)
HELLO => JGNNQ
평문(메시지)들의 공간(집합) { A,B,C---Z}
암호문들의 공간(집합) { A,B,C,….Z}
암호화 키들의 공간 { 0,1,2….25}=> 몇칸 밀리는가
복호화 키들의 공간 {0,1,2….25}
암호화/복호화는 각 키마다 서로 다른 일대일 함수!!\
>k=2인 경우
암호화 함수 X->X+2(mod 26)
복호화 함수 X->X-2(mod 26)
암호공격하기
- 특정 평문과 거기에 해당하는 암호문을 아는 경우
평문 : PLAY , 암호문 : RNCA => 뒤로 두칸 가는구나~
- 암호문만 아는경우
암호문 : SODB => 모든 경우의 수를 해본다.
SAGE구현
- AlphabeticStrings() 대문자만 사용하겠다.
- S= ShiftCryptosystem(AlphabeticStrings())-> shift암호 사용
- S.encoding() 소문자,특수문자( ' ',@,?,!) 를 소문자는 대무자로 , 특수문자는 삭제
- S.random_key()
- S.enciphering(K,P):암호화 (키,평문)
- S.deciphering(K,C): 복호화 (키,암호문)
Shift는 안전하지 않다.
대치암호
->A,B,C...Z를 마구 섞는 암호
암호화는 겹치지않게 보내야함
키들의 개수 ?
A->B 26개 B->25개 C->24개… 26X25… => 26!
공격하기
- 특정한 평문과 암호문을 아는경우 -> 쉽게 해결
- 암호문만 알고 있는 경우 -> 어렵다.
그럼 어떻게 공격? -> 빈도수를 이용한다.
DES
->블록암호 : 한글자씩 암호화 되지않고 여러 글자를 묶어서 함호화하는 방식
블록크기 : 2진법 64자리(아스키코드 : 256진법 8자리)
암호화키(=복호화키 ) : 2진법 56자리
AES
->블록크기 :2진법 128자리 (아스키코드 : 256진법 16자리)
암호화 키 (=복호화키) : 2진법 128,192,256 가능
RSA -> 암호화키와 복호화 키가 다르다.
합동 ( 두 정수 a,b를 n으로 나눈 나머지가 같을때)
거듭제곱 효율적으로 하기
M^17(mod n)계산하려면 곱셉 몇번?
-단순히 하면 16번 , 제곱으로 계산하면 5번만하면 됨
M^23(mod n)
-단순히 하면 22번 , 제곱으로 하면
RSA 공겨하기
1.n을 pq로 소인수분해 할수 있으면?
이걸 전개하면 p와 q의 합과 곱을 알기때문에 그 두 값을 알수있다.
결론-> n을 소인수분해 못하면 파이(n)을 구할수 없음
=> d를 알면 n을 소인수 분해 가능
고로 RSA구현할때 p와 q의 차이가 너무 적으면 안된다.
RSA의 안전함은 매우 큰 수 n의 소인수 분해가 아주 오래 걸린다는것이 핵심
하지만 매우 큰 소수를 만들어야되는데 => 소인수분해를 하지않고 소수를 만들어야됨
페르마/오일러 정리
P=3일때 a와 a^2는 둘다 1이다.
가로세로가 동일할때 다 1이나온다.
페르마 소정리
=>p가 소수이고 정수 a가 p의 배수가 아니면 a^p-1을 p로 나눈 나머지는 1
