소수란 1과 자기 자신만을 가지는 정수입니다. 소수를 구하는 알고리즘은 많지만 여기서 설명하는 알고리즘은 에라토스테네스의 체라고 불리는 알고리즘입니다. 에라토스테네스는 고대 그리스의 수학자로서 마치 체로 걸러 내는 것처럼 수를 걸러 낸다고 하여 에라토스테네스의 체라고 부릅니다.

이 방법은 아주 단순하지만 소수를 구하는데 효과적인 방법입니다.

원리

숫자 1 ~ 120 범위 안에 있는 소수를 모두 계산한다고 가정합니다.

  1. 1은 소수도, 합성수도 아닌 기초수이기 때문에 1을 제거합니다. 
  2. 2는 소수이므로 2를 다른 곳에 기록합니다.
  3. 자기 자신(2)를 제외한 2의 배수를 모두 지웁니다.
  4. 남아있는 수에서 2 다음인 수인 3부터 진행을 시작합니다.
  5. 3은 소수이므로 2를 기록한 곳에 기록합니다.
  6. 자기 자신(3)을 제외한 3의 배수를 모두 지웁니다.
  7. 3 다음의 수는 4이지만 2의 배수로 2번에서 지워졌으므로 남아있는 수에서 3 다음인 수인 5부터 진행을 시작합니다.
  8. 5은 소수이므로 2와 3을 기록한 곳에 기록합니다.
  9. 자기 자신(5)를 제외한 5의 배수를 모두 지웁니다.
  10. 위의 과정을 끝까지 반복하면 구하는 구간의 모든 소수가 남습니다.

위의 과정은 구하고자 하는 120까지의 수를 계속해서 지워나가는 방식입니다. 이 방식은 소수를 확실하게 구할 수 있지만 시간복잡도가 O(n^2)이 발생합니다. 여기서 에라토스테네스의 체를 이용하면 계산하는 범위를 줄일 수 있습니다.

에라토스테네스의 공식은 위 과정을 120까지 할 필요 없이 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 소수를 구할 수 있습니다. 따라서 위의 경우, 2, 3, 5, 7의 배수를 지우고 남은 수는 모두 소수입니다.

즉, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없습니다. 120에 루트를 씌우면 10.954451150103322의 값이 나오는데 이는 11보다 작으므로 11이하의 배수만 체크해도 소수를 구할 수 있습니다. 

코드

import math


def get_primes(n):
    # 구하고자 하는 수만큼 True를 갖는 리스트 생성
    is_primes = [True] * n
    # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산
    max_length = math.ceil(math.sqrt(n))

    for i in range(2, max_length):
        # True일 경우, 소수
        if is_primes[i]:
            # i이후 i의 배수들을 지워나감
            for j in range(i+i, n, i):
                is_primes[j] = False

    # 리스트의 True로 남아 있는 인덱스(소수)를 추출
    return [i for i in range(2, n) if is_primes[i]]


a = get_primes(10)
print(a)



파이썬에서 반올림은 보통 아래와 같이 구현합니다.

round(0.6)
# 1
round(2.4)
# 2


round()에 대해 찾아보면 자세한 내용이 있지만 간단하게 우리가 아는 반올림은 통계적인 반올림이고 파이썬의 round()는 수학적 반올림 값을 반환합니다. 이 때문에 나오는 결과에 대해서 사사오입 원칙이라고도 하는데 이를 설명하면 반올림 대상의 값이 5이고, 반올림 대상의 앞자리의 숫자가 짝수면 내림, 홀수면 올림을 진행합니다.

round(4.5)
# 4
round(0.5)
# 0
round(5.5)
# 6
round(1.5)
# 2


위 예시처럼 4.5는 반올림 대상의 앞자리가 짝수이므로 내림이 되었고 5.5에서는 5가 홀수이므로 올림이 되었습니다. 이러한 규칙을 모르고 반올림을 구한다면 시스템에 큰 오류를 범하고 문제 찾는거에 미궁이 빠지게 됩니다.

따라서 사람이 인식하고 있는 반올림을 구현하려면 내장 함수만으로는 불가능하고 반올림 함수를 직접 만들어야 합니다.

장고의 명령어 중, migrate, makemigrations 와 같은 명령어가 있습니다. 이러한 명령어는 models.py에 정의된 모델의 생성/변경 내역을 히스토리 관리데이터베이스에 적용 등과 같은 기능을 제공하여 손쉽게 데이터베이스의 구조를 바꿀 수 있습니다.

Migration 관련 명령어

# 마이그레이션 파일 생성
$ python manage.py makemigrations <app-name>

# 마이그레이션 적용
$ python manage.py migrate <app-name>

# 마이그레이션 적용 현황
$ python manage.py showmigrations <app-name>

# 지정 마이그레이션의 SQL 내역
 python manage.py sqlmigrate <app-name> <migration-name>

makemigrations

$ python manage.py makemigrations test

Migrations for 'test':
  test/migrations/0001_initial.py:
    - Create model Choice
    - Create model Question
    - Add field question to choice


makemigrations을 실행하면 모델을 변경시킨 사실 또는 새로 생성한 모델들과 같은 변경사항을 migrations로 저장하고자 Django에게 알려줍니다. migration은 Django가 모델의 변경사항을 저장하는 방법으로써, 디스크상의 파일로 존재합니다. 원한다면, <app-name>/migrations/0001_initial.py 파일로 저장된 새 모델에 대한 migration을 읽어볼 수 있습니다. 또 수동으로 Django의 변경점을 조정하고 싶을 때 직접 변경할 수 있습니다.


migration들을 실행시켜주고, 자동으로 데이터베이스 스키마를 관리해주는 migrate 명령어가 있습니다. 이 명령을 알아보기 전에 migration이 내부적으로 어떤 SQL 문장을 실행하는지 살펴봅시다. sqlmigrate 명령은 migration 이름을 인수로 받아, 실행하는 SQL 문장을 보여줍니다.

migrate

$ python manage.py migrate
Operations to perform:
  Apply all migrations: admin, auth, contenttypes, test, sessions
Running migrations:
  Rendering model states... DONE
  Applying test.0001_initial... OK


적용되지 않은생성/변경된 migrations들의 파일을 데이터베이스에 적용합니다. 이때 Django는 django_migrations 테이블을 두고 마이그레이션 적용 여부를 추적합니다. 이를 사용하면 데이터베이스를 직접 접근하지 않고도 모델의 반복적인 변경을 가능하게 해줍니다. 이처럼 마이그레이션을 만드는 명령과 적용하는 명령이 분리된 것은 버전 관리 시스템에 마이그레이션을 커밋하고 앱과 함께 출시할 수 있도록 하기 위해서라고 장고 공식 문서에 나와 있습니다.

모델의 생성/변경을 적용하는 단계는 아래와 같습니다.

  1. models.py 추가 및 변경
  2. python3 manage.py makemigrations를 실행해 변경사항에 대한 마이그레이션 파일 생성
  3. python3 manage.py migrate를 실행해 변경사항을 데이터베이스에 적용

showmigration

현재 적용된 마이그레이션 파일을 보여줍니다. 

$ python manage.py showmigrations

auth
[ ] 0001_initial
[ ] 0002_alter_permission_name_max_length
[ ] 0003_alter_user_email_max_length
[ ] 0004_alter_user_username_opts
[ ] 0005_alter_user_last_login_null
[ ] 0006_require_contenttypes_0002
[ ] 0007_alter_validators_add_error_messages
[ ] 0008_alter_user_username_max_length
contenttypes
[ ] 0001_initial
[ ] 0002_remove_content_type_name
sessions
[ ] 0001_initial


sqlmigrate

생성된 migrations파일들이 어떤 sql 문장을 실행하는지 보여줍니다.

$ python manage.py sqlmigrate test 0001

BEGIN;
--
-- Create model Choice
--
CREATE TABLE "test_temp" (
"id" serial NOT NULL PRIMARY KEY,
"name" varchar(200) NOT NULL
);
--
-- Create model Question
--
CREATE TABLE "test_temp2" (
"id" serial NOT NULL PRIMARY KEY,
"name" varchar(200) NOT NULL
);
--
-- Add field question to choice
--
ALTER TABLE "test_temp" ADD COLUMN "temp2_id" integer NOT NULL;
ALTER TABLE "test_temp" ALTER COLUMN "temp2_id" DROP DEFAULT;
CREATE INDEX "test_temp_7aa0f6ee" ON "test_temp" ("temp2_id");
ALTER TABLE "test_temp"
ADD CONSTRAINT "test_temp_temp2_id_246c99a640fbbd72_fk_test_temp2_id"
FOREIGN KEY ("temp2_id")
REFERENCES "test_temp2" ("id")
DEFERRABLE INITIALLY DEFERRED;

COMMIT;

만들어진 migrations의 sql은 아래와 같은 규칙이 있습니다.

  1. 테이블의 이름은 앱의 이름과 모델의 이름(소문자)가 조합되어 자동으로 생성. 위의 예시는 test 앱과 temp, temp2 모델명이 합쳐진 케이스
  2. 만약 pk가 지정되어 있지 않으면 자동으로 id라는 컬럼을 생성하고 pk로 지정
  3. 관례적으로 Djanngo는 외래키 컬럼의 마지막에 _id를 자동으로 추가
  4. sqlmigrate 명령어를 실행해도 실제로 데이터베이스의 마이그레이션을 실행하지 않음.


Django FilterSet 라이브러리는 GET 요청을 받고 쿼리 파라미터를 제어하는 기능을 제공합니다.

아래는 기본적으로 filterset을 사용한 예제입니다.

http://127.0.0.1:8000/test?name=kim


class NameFilter(filters.FilterSet):
    name = django_filters.CharFilter(
        name='name', lookup_expr='icontains'
    )


만약 위와 같은 구조가 아닌 여러 컬럼에 접근해야 한다면 아래와 같이 method를 지정하여 처리를 하도록 합니다.

http://127.0.0.1:8000/test?name=kim


class NameFilter(filters.FilterSet):
    name = django_filters.CharFilter(
        method='custom_name_filter'
    )

    def custom_name_filter(self, queryset, value, *args):
        return queryset.filter(name=args[0], nickname=args[0])


또는 아래와 같이 하나의 필드에 여러 값을 받은 다음 처리할 수 있습니다.

http://127.0.0.1:8000/test?multi=kim,5123



class MultiFilter(filters.FilterSet):
    multi = django_filters.CharFilter(
        method='custom_multi_filter'
    )

    def custom_multi_filter(self, queryset, value, *args):
        temp = args[0].split(',')
        name_list = []
        no_list = []
        
        for data in temp:
            if data.isdigit():
                no_list.append(int(data))
            else:
                name_list.append(data)

        return queryset.filter(name__in=name_list, no__in=no_list)


JWT

JWT(Json Web Token)은 토큰 기반 인증 방식으로, 사용자의 세션 상태를 저장하는 게 아니라 필요한 정보를 토큰 body에 저장해 사용자가 가지고 있고 그것을 증명서처럼 사용합니다. 사용자는 Access Token(JWT Token)을 헤더에 실어 서버로 보내게 됩니다.

토큰을 만들기 위해서는 Header, Payload, Verify Signature가 필요합니다.

  • Header: Header, Payload, Verify Signature 정보를 암호화할 방식(alg), 타입(type) 등이 들어감
    • JWT인 토큰의 유형이나 HMAC SHA256 또는 RSA와 같이 사용되는 해시 알고리즘이 무엇으로 사용했는지 등 정보가 담김
  • Payload : 서버에서 보낼 데이터가 들어감. 일반적으로 사용자의 ID, 유효기간이 포함
    • 클라이언트에 대한 정보, META data같은 내용이 들어있고, Base64로 인코딩 되어있음
  • Verify Signature : Base64 방식으로 인코딩한 Header, payload 그리고 SECRET KEY를 더한 후 서명됨

위 내용을 가진 최종적인 형태는 Encoded Header.Encoded Payload.Verify Signature (xxxx.yyyy.zzzz) 입니다.

header와 payload는 base64로 인코딩만 되므로 누구나 디코딩하여 확인할 수 있습니다. 따라서 payload에는 중요한 정보가 포함되면 안됩니다. 하지만 verify signature는 SECRET KEY를 알지 못하면 복호화할 수 없습니다. 

아래는 위 내용을 기반으로 인증하는 예시입니다.

사용자 A가 B의 데이터를 보고자 payload를 조작하려 합니다. payload에 있는 A의 ID를 B의 ID로 변경해 인코딩한 후, 서버에 해당 토큰을 전달합니다. 그러면 서버는 처음 암호화된 verify signature를 검사하게 됩니다. 여기서 payload는 B사용자의 정보가 들어있으나, verify signature는 A의 payload를 기반으로 암호화되어 있기 때문에 유효하지 않는 토큰으로 간주합니다. 따라서 A의 사용자는 SECRET KEY를 알지 못하는 이상 토큰을 조작할 수 없습니다.

JWT의 인증 방식은 아래의 단계와 같습니다.

  1. 클라이언트가 로그인을 위해 해당 정보를 서버에 전달
  2. 서버에서는 전달된 데이터로 사용자를 확인하고 사용자의 고유한 ID값을 부여한 후, 기타 필요한 정보와 함께 Payload에 추가
  3. JWT 토큰의 유효기간을 설정
  4. 암호화할 SECRET KEY를 이용해  Access Token을 발급
  5. 사용자는 Access Token을 받아 저장한 후, 인증이 필요한 요청마다 토큰을 헤더에 추가하여 전달

  6. 서버에서는 해당 토큰의 Verify Signature를 SECRET KEY로 복호화한 후, 조작 여부, 유효기간을 확인

  7. 해당 토큰이 유효하면 Payload를 디코딩하여 사용자의 ID에 맞는 데이터를 호출

세션/쿠키 방식과 가장 큰 차이점은 세션/쿠키는 세션 저장소에 유저의 정보를 넣는 반면, JWT는 토큰 안에 유저의 정보를 넣는다는 점입니다. 사용자 입장에서는 헤더에 세션ID나 토큰을 실어서 보내준다는 점에서는 동일하나, 서버 측에서는 인증을 위해 암호화를 하냐, 별도의 저장소를 이용하냐는 차이가 발생합니다.

장점

1. JWT는 발급한 후 토큰 검증만 하면 되기 때문에 추가 저장소가 필요 없음

2. 서버를 확장하거나 유지,보수하는데 유리

3. 토큰 기반으로 하는 다른 인증 시스템에 접근이 가능

  • 예를 들어 Facebook 로그인, Google 로그인 등은 모두 토큰을 기반으로 인증. 선택적으로 이름이나 이메일 등을 받을 수 있음

단점

1. 세션/쿠키의 경우 세션ID가 변질되었다고 판단되면 해당하는 세션을 지우면 되지만 JWT는 한 번 발급되면 유효기간이 완료될 때 까지는 계속 사용이 가능하므로 유효기간이 지나기 전까지  정보들을 탈취할 수 있음

  • 기존의 Access Token의 유효기간을 짧게 하고 Refresh Token이라는 새로운 토큰을 발급하면 Access Token을 탈취당해도 상대적으로 피해를 줄일 수 있음

2. payload 정보가 제한적 Payload는 따로 암호화되지 않기 때문에 디코딩하면 누구나 정보를 확인할 수 있어서 담는 데이터가 제한적임 

3. 세션/쿠키 방식에 비해 JWT의 길이가 기므로 인증이 필요한 요청이 많아질수록 서버의 자원낭비가 발생

4. 단점 1번과 연관된 문제로 유효기간을 짧게 하면 재로그인 시도가 잦아지고 길면 해커에게 탈취될 가능성이 큼

Refresh Token

Access Token(JWT)를 통한 인증 방식의 문제로 탈취당할 경우 보안에 취약하다는 점입니다. 유효기간이 짧은 Token의 경우, 사용자는 새 Token을 발급받기 위해 로그인을 자주 시도해야 하고 유효기간을 늘리면, 탈취당했을 때 보안에 취약해지게 됩니다. '유효기간을 짧게 하면서 보안을 챙길 수 있는' 물음에 나온 방식이 Refresh Token입니다.

Refresh Token은 Access Token과 똑같은 형태의 JWT입니다. 로그인이 완료됐을 때, Access Token과 동시에 Refresh Token은 긴 유효기간을 갖고 발행되고 Access Token의 유효기간이 만료되었을 때 새로 Token을 발급해주는 열쇠가 됩니다. 

예를 들어, Refresh Token의 유효기간은 2주, Access Token의 유효기간은 1시간으로 설정하게 되면 사용자에게 발급된 Token이 1시간이 지나게 되면 Access Token은 만료되지만 Refresh Token의 유효기간은 아직 남아 있기 때문에 사용자의 재로그인 없이 Access Token을 새롭게 발급받을 수 있습니다. 

위의 예제와 같이 Refresh Token의 유효기간이 만료되면 사용자는 새로 로그인해야 하고 Access Token과 동일하게 Refresh Token도 탈취될 가능성이 있기 때문에 적절한 유효기간 설정이 필요합니다.

 

아래는 Refresh Token이 포함된 JWT 인증 방식입니다. (1~3번은 JWT와 동일)

  1. 클라이언트가 로그인을 위해 해당 정보를 서버에 전달
  2. 서버에서는 전달된 데이터로 사용자를 확인하고 사용자의 고유한 ID값을 부여한 후, 기타 필요한 정보와 함께 Payload에 추가
  3. JWT 토큰의 유효기간을 설정
  4. 암호화할 SECRET KEY를 이용해  Access Token, Refresh Token을 발급 (일반적으로 회원 DB에 Refresh Token을 저장)
  5. 사용자는 Refresh Token을 안전한 저장소에 저장
  6. 사용자는 Access Token을 받아 저장(쿠키)한 후, 인증이 필요한 요청마다 토큰을 헤더에 추가하여 전달

  7. 시간이 지나 Access Token이 만료되었다고 가정

  8. 사용자는 6번과 같은 방식으로 Access Token을 헤더에 담아 서버에 요청

  9. 서버는 Access Token이 만료된 것을 확인하고 사용자에게 만료 메세지를 반환

    1. 사용자는 Access Token의 payload를 통해 유효기간을 알 수 있으므로 요청 이전에 바로 재발급 요청을 할 수 있음

  10. 사용자는 Refresh Token과 Access Token을 헤더에 담아 서버에 요청

  11. 서버는 요청받은 토큰의 Verify Signature를 SECRET KEY로 복호화한 후, 조작 여부, 유효기간을 확인하고 전달받은 Refresh Token과 저장해둔 Refresh Token을 비교. Token이 동일하고 유효기간이 지나지 않았다면 Access Token 발급

  12. 사용자는 새로 발급받은 Access Token을 저장하여 인증이 필요한 요청마다 토큰을 헤더에 추가하여 전달

장점

1. Access Token이 있을 때보다 안전

단점

1. 구현이 복잡

2. Access Token이 만료될 때마다 새롭게 발급하는 과정에서 생기는 HTTP 요청이 잦음

'보안 & 보안' 카테고리의 다른 글

서버 인증 (JWT)  (0) 2019.08.17
서버 인증 (세션/쿠키 기반)  (0) 2019.08.17
SSL Pinning  (0) 2018.12.18
TLS (Transport Layer Security)  (0) 2018.12.18
스니핑  (0) 2017.04.12
패스워드 크래킹  (0) 2017.03.28

인증은 왜 필요할까?

A와 B의 유저가 은행 사이트에서 각 본인의 잔액을 확인하기 위해 로그인을 하고 본인들의 잔액을 확인할 수 있습니다. 여기서 로그인은 A와 B를 구분하는 인증으로 볼 수 있습니다. 또한, A의 잔액을 B나 다른 사용자에게 노출시키면 안되므로 보안으로도 볼 수 있습니다. 현재 가장 많이 사용하는 통신 방식은 HTTP 방식입니다. HTTP의 특징으로 stateless가 있습니다. 이러한 특징으로 인해, 만약 은행 사이트에 인증과 관련된 내용이 없다면 로그인을 한 뒤에 메인 페이지로 이동했을 시, 정보가 사라져 어느 사용자인지 알 수 없습니다. 따라서 사용자마다 다른 정보를 노출하고 저장할 때, 인증은 필수적으로 가져가야 합니다. 아래에서는 다양한 인증 방식과 장단점을 설명합니다.

헤더에 사용자 정보를 추가하여 전달

사용하면 안되는 방식입니다. 로그인 이후에도 다른 페이지를 이동할 때마다 사용자의 정보를 헤더에 추가하여 서버에 전달하는 방식입니다. 개발 초기에 내부에서 테스트를 진행할 때나 사용할 수 있는 방식으로 이러한 방식으로 실제 서비스 운영이 된다면 사용자의 개인정보를 그대로 노출시켜 보안 문제를 발생시킵니다.

장점

1. 인증 방식을 고려할 필요가 없음

2. 편함

단점

1. 보안에 매우 취약

2. 요청이 올 때마다 서버는 전달받은 데이터로 해당 유저가 맞는지 검증해야 하므로 비효율적

세션/쿠키 기반 인증 방식

서버의 세션과 사용자 쿠키를 기반으로 하는 인증 방식입니다.

인증 방식은 아래의 단계와 같습니다.

  1. 클라이언트가 로그인을 위해 해당 정보를 서버에 전달
  2. 서버는 정보를 읽어 사용자를 확인하고 로그인 성공 시, 사용자를 식별할 수 있는 고유한 세션 ID를 생성하고 이를 메모리나 DB에 저장
    1. 저장하는 곳을 세션 저장소라고 하고 보통 Redis를 많이 사용함
  3. 서버는 요청의 결과값으로 세션 ID를 사용자에게 전달
  4. 세션 ID를 전달받은 사용자는 쿠키에 해당 값을 저장
  5. 이후 다른 페이지 이동이나 사용자 인증이 필요할 때, 헤더에 해당 쿠키를 실어서 전달
  6. 서버는 쿠키를 받아서 세션 저장소에 저장이 된 쿠키(세션ID)인지 확인
  7. 유효한 쿠키(세션ID)일 경우, 요청받은 데이터를 반환

Redis를 세션 저장소로 사용한다면 세션ID가 서버의 메모리에 저장이 됩니다. 만약 서버 확장 시, 모든 서버가 세션 저장소에 접근할 수 있도록 중앙 세션 저장소 관리가 필요합니다.

장점

1. 쿠키가 포함된 요청이 외부에 노출되어도 쿠키(세션ID)는 유의미한 값을 갖고 있지 않기 때문에 쿠키 자체로 큰 문제를 발생시키지 않음

2. 요청을 주는 각 사용자마다 고유의 세션ID가 발급되어 일일이 회원정보를 확인할 필요 없음

단점

1. 장점 1번에서 쿠키 자체는 유의미하지 않아 노출되도 큰 문제가 없다고 했으나, 사용자 A가 보낸 요청을 해커가 탈취(하이재킹)하여 해당 쿠키로 서버에 변질된 내용으로 HTTP요청을 보내면 서버는 해커의 요청을 A 사용자로 인식하게 됨

  • 이를 방지하기 위해 세션의 유효시간을 추가하거나 HTTPS를 사용해 탈취해도 안의 정보를 읽기 힘들게 만들 수 있음

2. 서버에서 세션 저장소를 사용하므로 추가적인 저장공간을 필요로 함

3. 중앙 세션 저장소 관리가 없으면 시스템 확장이 어려움

4. 중앙 세션 저장소에 장애가 발생하면 인증 전체가 문제가 될 수 있음

만약 세션을 사용하지 않고 쿠키만으로 인증을 한다면?

사용자가 로그인 시, 서버는 ID, PWD와 같은 값을 암호화 또는 인코딩으로 변환하여 사용자에게 전달하고 사용자는 이를 쿠키에 저장합니다. 그리고 인증이 필요할 때마다 이 쿠키를 헤더에 담아서 서버에 요청을 하고 서버는 해당 쿠키를 복호화 또는 디코딩으로 풀어 사용하게 됩니다. 여기서 문제는 쿠키가 유의미한 값을 갖게 되기 때문에 외부에 노출이 된다면 헤더에 사용자 정보를 전달하는 방식과 같은 문제를 띄게 됩니다.

'보안 & 보안' 카테고리의 다른 글

서버 인증 (JWT)  (0) 2019.08.17
서버 인증 (세션/쿠키 기반)  (0) 2019.08.17
SSL Pinning  (0) 2018.12.18
TLS (Transport Layer Security)  (0) 2018.12.18
스니핑  (0) 2017.04.12
패스워드 크래킹  (0) 2017.03.28

+ Random Posts