아인스트라세의 SW 블로그

Rust 개발 환경 구축(Windows10에서 Sublime Text 3 / VS code)

2020. 4. 5. 02:09

느닷없이 Rust를 배우고 싶어져서 Rust 개발환경을 한번 구축해보도록 하겠습니다.

사실 지금 글을 쓰는 이 시점에는 Rust를 공식적으로 지원하는 IDE나 그런 녀석들은 잘 없는데, 그래도 제일 많이 쓰이는 조합이 Visual Studio Code + Rust plugin인 것 같다. 해당 조합은 VS코드에서 Syntax highlighting을 지원합니다.

그리고 RLS라는 Rust Language Server라는 녀석이 있는데 이 녀석은 백그라운드로 실행되면서 코드 에디터나 다른 툴에게 Rust에 대한 정보를 넘겨주는 그런 녀석입니다. syntax상 에러 같은거를 알려주고, 선언부로 이동하기 라던지 IDE에서 제공하는 기능들을 모듈화 된 프로그램이라고 보면 됩니다.

근데 아직 RLS도 Stable 버전이 나온 상태는 아니라서 다른 언어에 비해좀 느리거나 중간에 동작하지 않거나 하는 경우가 좀 있다고 합니다. 그래도 쓸만하다고 하네요.

제가 구축할 환경은 Windows 10 + Sublime Text3 + Rust plugin 이 되겠습니다.

Rustup 설치

Rustup은 rust 툴체인 인스톨러라고 합니다. Rustup을 쓰지 않더라도 러스트를 설치할 수 있지만, rustup을 이용하면 다른 컴포넌트들을 쉽게 설치할 수 있어서 추천한다고 합니다.

https://rustup.rs/

rustup.rs - The Rust toolchain installer

To install Rust, if you are running Unix, run the following in your terminal, then follow the onscreen instructions. curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

rustup.rs

홈페이지로 가서 다운받은 뒤 설치를 완료해봅시다.

만약 WSL를 사용하시는 분이라면 아래 curl로 시작하는 명령어를 치라고 하네요. 저는 고전 방식으로 rustup-init.exe를 다운받은 뒤 설치를 진행해보도록 하겠습니다.

1번을 선택한 뒤 계속 진행해보도록 하겠습니다.

설설치가 완료된 뒤 cmd창에서 rustc라고 쳐보도록 하겠습니다.

rustc 컴파일러가 설치된 것을 확인할 수 있네요.

Sublime text3에 Rust 플러그인 설치

Rust 플러그인은 Sublime text 3이전 버전은 지원할 계획이 없다고 합니다.

서브라임 택스트에서 Ctrl + Shift + P를 누르면 명령 창이 나타나게 됩니다.

여기서 Package install을 입력한 뒤, Package Control: Install Package를 선택하고 엔터를 눌러봅시다.

그러면 패키지 목록들이 나타나는데, 그 중 Rust enhanced를 설치해보도록 하지요.

조금 기다리면 설치가 완료됩니다.

Rust 프로젝트 만들기

서브라임 텍스트는 단순 에디터이니, 터미널을 통해서 프로젝트를 생성해줍니다.

그리고 서브라임 텍스트로 프로젝트 디렉토리를 열어줍니다.

$ cargo new hello_world --bin
$ subl ./hello_world

Sublime Text3를 위한 RLS 설치 및 연동

설치

Rust는 nightly, beta, stable의 3가지 버전이 있는데 unstable한 기능들은 nightly rust에서만 가능하다고 합니다. RLS가 아직 unstable해서 그런지 nightly rust에서만 사용이 가능하다고 합니다.

nightly rust toolchain를 사용해야 하는데, 만약 설치가 되어 있지 않다면 다음 과정에서 설치가 됩니다.

Nightly rust tool-chain은 rustup을 이용해서 설치를 할 수 있는데, 저는 이미 stable이 rustup설치시 같이 설치가 된 상태인 것 같군요.

다음 명령어로 설치된 toolchain 상태들을 알 수 있습니다.

$ rustup show

그리고 다음 명령어로 nightly toolchain으로 설정할 수 있습니다.

$ rustup default nightly

만약 nightly 툴체인이 설치되어 있지 않다면 설치도 같이 진행을 합니다.

그리고 나서 RLS를 설치합니다.

$ rustup update
$ rustup component add rls rust-analysis rust-src

그리고 rls가 제대로 동작하는지를 다음 명령어로 확인합니다.

$ rustup run nightly rls --version
rls 1.41.0 (5fde462 2020-02-21)

이제 RLS가 잘 설치된 것 같군요.

서브라임 텍스트와의 연동

서브라임 텍스트에서 RLS와 연동하려면 Package Control에서 LSP라는 녀석을 설치하면 됩니다.

아까처럼 Ctrl+shift+p로 명령어창을 띄운 뒤 , package install을 치고 엔터를 누릅니다.

좌측 하단에 Progress bar가 나타난뒤, 패키지 목록 검색 창이 뜨면 LSP를 고르면 됩니다.

Detail 설명란에 Language Server Protocol이라고 나와있는 녀석입니다.

설치가 완료되면 위와 같은 메시지가 뜨네요.

그리고 LSP for Rust를 활성화를 시켜줘야 하는데, Rust Project를 아무거나 열고, main.rs나 lib.rs같은 파일을 하나 엽니다.

그리고 아까처럼 커맨드 팔렛트를 연뒤 (Ctrl+Shift+P) LSP:Enable 로 검색하면 아래와 같이 뜹니다.

둘 중 하나를 고르면 됩니다. 이 프로젝트에서만 활성화 할 것인지, 아닌지를 고를 수 있네요.

그리고 언어도 골라야하는데, rust를 선택해줍니다.

어허 또 무슨 에러일까요.

RLS가 실행이 안되어서 그런 것 같으니, 터미널을 하나 열어서 따로 실행을 시켜줍니다.

실행을 하고 나서 다시 LSP: Enable 설정을 해 주면 설정이 완료되었습니다.

RLS가 잘 동작하는지 확인해보기위해서, rs 확장자로 된 파일에 적당히 수정을 해 보도록 하겠습니다.

use std::fmt;를 추가해주고 저장을 하니 unsed import라고 warning이 뜨는군요. RLS가 잘 설정된 것으로 보입니다.

Visual Studio Code 를 위한 RLS 설치 및 연동

VS Code에서 RLS 설치 및 연동은 서브라임 텍스트에 비해 비교적 쉬운편입니다.

일단 Visual Studio Code와 Rustup가 설치가 되어있다는 가정하에 진행해보도록 하겠습니다.

VScode에서 Rust Extension을 설치해보도록 하겠습니다. Ctrl + P를 눌러서 ext install rust를 입력해서 검색을 합니다.

이중에서 Rust (rls)를 눌러서 Install을 합니다.

설치가 다 된 이후 reload를 하면 되는데 Ctrl + Shift + P를 눌러서 커맨드 팔렛트를 연 뒤 reload를 치면 됩니다.

그리고 Rust 프로젝트 디렉토리를 열면 자동적으로 Rustup component를 설치하려고 합니다.

rs 확장자로 된 파일을 하나 열면 아래에 저런 창이 뜹니다.

rustup을 찾지 못하는 것 같으니, nightly를 아까 서브라임 환경 설정할 때 처럼 설정해주도록 합시다. 아니면 VS code를 다시 시동을 하면 아마 인식을 할 것 같네요.

이제는 Rustup을 못찾는다는 이야기는 안하고 RLS가 설치되어 있지 않다고 합니다. Yes를 눌러서 설치를 해줍니다.

터미널에 무언가가 뜨면서 설치가 진행되는 것 같습니다.

설치가 완료되었네요. 좌측 하단 상태바에서도 RLS가 돈다고 뜹니다.

저런 tooltip도 뜹니다. 성공적으로 된 것 같네요.

빌드와 실행도 잘 됩니다.

굿!

https://github.com/sublimelsp/LSP

https://rinthel.github.io/2017/08/20/rust-vscode-macos/

https://github.com/rust-lang/rustup
https://github.com/rust-lang/rust-enhanced

저작자표시

'개발 & CS 지식' 카테고리의 다른 글

코딩이란 무엇일까? (0)	2020.07.24
[철봉여지도] 평행봉 및 철봉 지도 개발기 (3)	2020.06.12
Visual Studio 2019/2022에서 콘솔창 바로 닫히는 현상 방지 (0)	2020.02.26
MS-SQL SSMS를 활용한 튜토리얼 (0)	2020.01.19
Microsoft SQL Server 2019 Express 설치 + SSMS (0)	2020.01.19

Google Kickstart Round A 2020 풀어보기

2020. 3. 31. 21:39

저저번주쯤 주말에 올해 2020년의 첫 킥스타트 라운드 A가 있었는데, 아무것도 모르고 주말에 잠을 퍼질러 자다가 참여를 못하게 되었다.

A라운드는 근데 문제 난이도가 낮아서 빨리풀기 대회였다니 뭐 이런이야기들을 들었는데, 대회 당시에는 참여를 못했지만 나중에 업솔빙이라도 해볼 겸 시간 날때 풀어보았다.

이번해의 킥스타트는 저번과는 다르게 Large dataset도 제출한 뒤 바로 full-feedback을 준다고 한다. 맞았는지 틀렸는지를 바로 알려준다는 것은 뭔가 좋은 것 같으면서도 안 좋은것 같기도 하다.

바로 한번 문제 풀어보도록 하겠다.

문제들은 여기에서 확인하고 다시 풀어볼 수 있다.

총 4문제가 있다. 정답률을 보니 난이도가 왼쪽 < 오른쪽 문제로 가는 것 같다.

1. Allocation

문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?

그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. //(O(NlgN)//)로 풀리며, N이 //(10^5//)이므로 쉽게 풀린다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int A[100005];
void solve() {
	int N, B;
	cin >> N >> B;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (B >= A[i]) {
			B -= A[i];
			ans++;
		}
		else {
			break;
		}
	}
	printf("%d\n", ans);
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

2. Plates

접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.

dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서 dp가 맞는 듯 했다.

2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.

//(dp[i][j]//)는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수

이러면 //(dp[i][j]//)를 이용해서 다음 줄에서 k개의 접시를 구하는 경우//(dp[i+1][j+k]//)를 쉽게 구할 수 있다.

for-loop를 돌리는 식으로 구현해보았다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
	int N, K, P;
	cin >> N >> K >> P;
	memset(dp, 0, sizeof(dp));
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> a[i][j];
			a[i][j] += a[i][j - 1];
		}
	}

	
	for (int i = 1; i <= K; i++) {
		dp[1][i] = a[1][i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= i * K; j++) {
			for (int k = 0; k <= K; k++) {
				dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
			}
		}
	}
	printf("%d\n", dp[N][P]);
	return;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

3. Workout

이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때 수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.

최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.

인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.

그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

int M[100005];
int N, K;
bool ok(int v) {
	int k = K;
	for (int i = 1; i < N; i++) {
		int diff = M[i] - M[i - 1];
		k -= (diff + v - 1) / v - 1;
	}
	return k >= 0;
}
int solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> M[i];
	}
	int l = 1;
	int r = 1e9;
	while (l < r) {
		int m = (l + r) / 2;
		if (ok(m)) {
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	return r;
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}

4. Bundling

문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..

K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.

A A A B C C C D E E E F

이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.

솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.

A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.

조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.

Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.

그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 2000006
class Node {
public:
	char c;
	int num;
	int next[28];
	Node() {
		clear();
	}
	void clear() {
		memset(next, 0, sizeof(next));
		num = 0;
		c = 0;
	}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
	auto& cnode = nodes[v];
	int ret = cnode.num / k;
	for (char c = 'A'; c <= 'Z'; c++) {
		if (cnode.next[c - 'A'])
			ret += dfs(cnode.next[c - 'A'], k);
	}
	return ret;
}
int solve() {
	int n, k;
	cin >> n >> k;
	//clear prev data
	for (int i = 0; i <= cnt; i++) {
		nodes[i].clear();
	}
	cnt = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int ptr = 0;
		for (char c : s) {
			auto& next = nodes[ptr].next[c - 'A'];
			if (!next) {
				next = ++cnt;
				nodes[next].c = c;
			}
			ptr = next;
			nodes[ptr].num++;
		}
	}
	
	return dfs(0, k);
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}

저작자표시

'알고리즘 & Problem Solving' 카테고리의 다른 글

Google Codejam Kickstart 2020 Round B 후기 (0)	2020.04.22
Google Codejam 2020 Qualification Round 후기 (0)	2020.04.05
백준 1854번 K번째 최단경로 찾기 문제 풀이 (0)	2020.02.26
백준 1753번 문제 '최단경로' 풀이 (0)	2020.02.26
백준 1087번 문제 쥐잡기 풀이 (0)	2020.02.18

Hash Length extension attack - 길이 확장 공격

2020. 3. 31. 20:57

CTF에서 크립토계열 문제들을 보면 이따금씩 등장하는 공격기법이다.

딱히 어려운 공격법은 아니니 곧바로 예시를 들면서 설명을 들어가자.

HMAC(Hash-based Message Authentication Code)

HMAC이 뭐냐면 Hash 기반의 MAC이다. 여기서 MAC은 Message Authentication Code인데, 일종의 전자서명이라고 보면 된다.

만약 A라는 사람이 B에게 "마트에서 계란 5개 사와"라는 메시지를 보낸다고 치자. 그런데 이 메시지가 B에게 도착했는데, A가 보낸게 맞고 다른 공격자가 임의로 변조시킨 메시지가 아니라는것을 알고 싶다고 하자.

이때 쓰이는 것이 MAC이다. A와 B가 공통적으로 공유하는 키 값이 있다고 하고, 공격자는 이 키를 모른다고 하자.

그러면 A는 메시지를 보내면서 key 값 뒤에 메시지를 붙인 뒤 해쉬를 취한 값으로 서명값을 만든다.

다음과 같은 모양이 나오게 된다.

signature = sha256( key + message )

만약 공유하는 비밀 키의 내용이 "CarpeDiem"이라고 하자.

그러면 서명값은 sha256("CarpeDiem마트에서 계란 5개 사와") 의 값이되게 된다.

그리고 이 서명값을 메시지와 같이 보낸다고 하자.

그러면 B는 메시지와 서명값을 받고, 본인이 가지고 있는 키를 기반으로 서명값을 만들었을때 이 서명값이 전달된 서명값과 일치하면 이 메시지는 A가 만든것이 맞다는 것을 알 수 있다.

공격자는 A와 B가 공유하고 있는 키 값을 알 수 없으므로 정당한 서명값을 만들 수 없다.

Hash Length extension attack

이러한 HMAC을 쓰는 경우 특정 조건이 맞으면 이 해쉬 길이 확장공격을 사용할 수 있다.

이 공격으로 공유되는 비밀 키 값은 알수가 없지만, 어떤 메시지와 서명값의 쌍을 안다면 메시지 뒤에 다른 문자열이 추가된 메시지와 그에 맞는 정당한 서명값을 만들 수 있다.

사전 조건

공격을 하기 위해 필요한 조건들은 몇 가지 정보들이다. 다음 내용들을 알면 공격이 가능하다.

1. 키의 길이

2. message의 내용

3. message에 대한 정당한 서명값

4. 해시 알고리즘의 종류가 Merkle-Damgard construction에 기반한 것들(MD5, SHA-1, SHA-2)

만약 아까 이야기한 예시를 계속해서 들면 키의 길이가 CarpeDiem인 것은 모르더라도 9글자인 것을 알고, "마트에서 계란 5개 사와"가 메시지인 것을 알고, 이 메시지에 대한 서명 값이 0xdeadbeef라는 것을 안다고 가정하자.

그러면 이 정보를 바탕으로 공격자는 뒤에 공격자가 원하는 메시지가 추가된 메시지와 서명값을 만들어낼 수 있다.

가령 공격자가 "그리고 고기도 2kg 사와"라는 메시지를 뒤에 추가하려고 한다고 하자.

그러면 이 공격을 통해서 공격자는 "마트에서 계란 5개 사와 그리고 고기도 2kg 사와"라는 메시지에 대한 정당한 서명값을 알아낼 수 있다.

실제로는 기존 문장과 추가 된 문장 사이에 Null byte 값들이 여러개 추가될 수 있다.

공격 예시

여기서 설명하는 내용은 위키 백과와 같은 예시이다.

원래 데이터가 아래와 같다고 하자

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo

Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

여기에 공격자는 마지막에 파라메터를 추가하고자 한다.

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

그러면 공격이 이루어진 데이터는 다음과 같은 형태를 띄게 된다.

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x02\x28&waffle=liege

New Signature: 0e41270260895979317fff3898ab85668953aaa2

사이에 Null byte들이 많이 들어가게 되는데, 저 Null byte로 해시함수를 계산할때 내부 구조를 적절히 바꾸어서 하는 방식이라고 한다.