|  책 이름 ㅣ 가장 빨리 만나는 코어 자바 9

|   해볼 것 들   |

JShell 활용

Java 가변 인수

Factory Method -> ex) getInstance()

자바 문서화 주석 , javadoc, ex ) @author

클래스 주석, 메서드 주석, 변수 주석, 일반 주석, 링크, 

람다 표현식 ( 메서드 참조, 생성자 참조 , 지연 실행 구현, 함수형 인터페이스 선택, ), 람다표현식과 에러처리

super 을 이용한 메서드 표현식 

super::work

자바 예외 처리

메소드에서 예외를 던지는 것이 더 낫다고 ??

" 빨리 던지고, 늦게 잡아내라 "

자바와 로깅

자바 제네릭 메서드 와 타입 경계

T extends A 하면 T는 A의 서브타입임이 보장된다.

서버 타입 와일드 카드

? extends A 

자바 정규표현식

애너테이션 과 JUNIT

@ 이런애들

Nashorn

RSA에 대해 공부하기 전에 이 문제를 봤을 땐 시도할 엄두가 안나서 넘겼었는데

요번주에 RSA에 대해서 배운 후 다시 이 문제를 풀어보았다.

출제자의 의도는 hint = (d+q)^(d-q) 에서 xor 특징을 이용한 bit 관련 BF 공격이였다.

( 사실 이 공격방법은 아직 이해를 못하였다. )

하지만 출제자가 문제를 잘못내서 gint만 가지고도 문제를 풀 수 있었고

대부분의 라이트업이 그렇게 풀어져 있었다.

하지만 라이트업들이 뭔가 조금씩 부족한 부분이 있어서 애를 먹었는데

한번 내가 이해한 그대로 블로그에 자세히 기록해두겠다.

1. 문제 요약 

N = pq ( p,q is prime )

e that satisfy ((p-1)(q-1), e) = 1

d = e modular inverse at N

Public Key ( N, e ) 와 g = d(p-0xdeadbeef)를 알 때, enc_flag = flag^e mod N 를 복호화해라.

전형적인 RSA 문제이다. 

우리는 어떻게 N을 소인수 분해할까를 먼저 고민하는데 

0xdeadbeef를 c ( 상수 )라 두면

(p-c) 

우리는 여기서 페르마의 소정리를 활용할 생각을 해보아야 한다.

페르마의 소정리 : a^(p-1) mod p = 1

증명 : 생략

그리고 RSA 암호화, 복호화에 이용되는 성질인 M^ed mod N = M 에 대해서도 활용하여야 한다.

a^eg = a^ed(p-c)

a^eg ≡ a^(p-c) ( mod N )  ∵ a^ed mod N = a

a^eg * a^(c-1) ≡ a^(p-1) ( mod N )

a^(p-1) mod N = r ⇔ a^(p-1) = kN + r

a^(p-1) mod p = 1 ⇔ kN+r mod p = 1 ⇔ r mod p = 1 ⇔ r = kp + 1

⇔ a^(p-1) mod N = kp+1 

( cf. k는 그냥 상수라고 보고 의미없으니 그냥 넘기자 )

a^(p-1)mod N - 1 = kp

(a, N) = 1을 만족하고 그외 앞에 식의 조건들을 만족시키는 수들중 가장 작은 a = 2

2^(eg + (c - 1)) mod N - 1 = kp

(kp, N) = p (  ∵ if k = q, a^(p-1) mod N > N -> false )

그러면 p를 구할 수 있다.

p를 구하면 q = n/p 부터 시작해서 d까지 모두 구해낼 수 있다.

페이로드는 파이썬으로 짜보았다

RSABaby.py

정수 배열과 타겟 숫자가 주어지면, 

합이 타겟값이 되는 두 원소의 인덱스를 찾으시오.

단, 시간복잡도 O(n) 여야 합니다.

예제)

Input: [2, 5, 6, 1, 10], 타겟 8

Output: [0, 2] // 배열[0] + 배열[2] = 8

문제를 처음 보았을 때 어 간단한데? 라고 생각했는데

풀려고 끄적대보니 O(n)만 쓰는 방법이 생각 안나서 결국 풀이를 봤는데

해시맵 실화야? 허허.,...

시간 복잡도: O(n). 해쉬맵의 containsKey 는 보편적으로 O(1). O(n)*O(1) = O(n).

공간 복잡도: O(n)

문제의 풀이는 다음과 같다.

계속 돌면서 타켓 - 현재 인덱스 값 을 해시맵에서 찾는다.

나오면 끝, 안나오면 계속 돈다. 

그러면 O(n)안에 나오게 된다.

와우...