Nothing Special   »   [go: up one dir, main page]

KR100720726B1 - Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법 - Google Patents

Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법 Download PDF

Info

Publication number
KR100720726B1
KR100720726B1 KR1020030070103A KR20030070103A KR100720726B1 KR 100720726 B1 KR100720726 B1 KR 100720726B1 KR 1020030070103 A KR1020030070103 A KR 1020030070103A KR 20030070103 A KR20030070103 A KR 20030070103A KR 100720726 B1 KR100720726 B1 KR 100720726B1
Authority
KR
South Korea
Prior art keywords
secret key
mod
value
message
rsa algorithm
Prior art date
Application number
KR1020030070103A
Other languages
English (en)
Other versions
KR20050034238A (ko
Inventor
진원일
허미숙
정배은
임범진
이경희
Original Assignee
삼성전자주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성전자주식회사 filed Critical 삼성전자주식회사
Priority to KR1020030070103A priority Critical patent/KR100720726B1/ko
Priority to US10/959,993 priority patent/US7421074B2/en
Publication of KR20050034238A publication Critical patent/KR20050034238A/ko
Application granted granted Critical
Publication of KR100720726B1 publication Critical patent/KR100720726B1/ko

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/723—Modular exponentiation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/14—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/002—Countermeasures against attacks on cryptographic mechanisms
    • H04L9/003—Countermeasures against attacks on cryptographic mechanisms for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7223—Randomisation as countermeasure against side channel attacks
    • G06F2207/7233—Masking, e.g. (A**e)+r mod n
    • G06F2207/7242—Exponent masking, i.e. key masking, e.g. A**(e+r) mod n; (k+r).P
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/08—Randomization, e.g. dummy operations or using noise

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Computing Systems (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Storage Device Security (AREA)

Abstract

RSA알고리즘을 이용한 보안유지시스템이 개시된다. 본 보안유지시스템은, 입력된 메시지의 암호화 및 복호화 중 어느 하나의 경우에 사용되는 비밀키 및 공개키를 수신하는 키입력부, 비밀키를 제1비밀키 및 제2비밀키로 분할하는데 사용되는 랜덤계수를 생성하는 랜덤계수생성부, 생성된 랜덤계수를 이용하여 비밀키를 제1비밀키 및 제2비밀키로 나누고, 이를 사용하여 RSA 알고리즘의 멱승 연산을 수행하는 제1연산부, 및 제1비밀키 및 상기 제2비밀키를 사용하여 각각 멱승 연산된 결과를 RSA 알고리즘의 멱승연산식에 반영하여, 메세지의 암호화처리 및 복호화처리 중 어느 하나를 수행하는 제2연산부를 포함한다. 이에 따라, DPA 공격시 공격자가 중간 결과 예측이 불가능해진다.
RSA 알고리즘, DPA(Differential Power Analysis), 멱승(exponentiation).

Description

ＲＳＡ 알고리즘을 이용한 보안유지시스템 및 그 방법 { Security system using ＲＳＡ algorithm and method thereof }
도 1은 기존의 RSA 알고리즘 중에서 상위 비트부터 하위 비트 방향으로 멱승 연산을 수행하는 흐름도,
도 2는 기존의 RSA 알고리즘 중에서 하위 비트에서 상위 비트 방향으로 멱승 연산을 수행하는 흐름도,
도 3은 본 발명에 따라 DPA(Differential Power Analysis)공격을 대비한 RSA 알고리즘 암호화 장치,
도 4는 본 발명에 따라 DPA 공격을 차단하는 RSA 알고리즘의 일실시예의 흐름도, 그리고,
도 5는 본 발명에 따라 DPA 공격을 차단하는 RSA 알고리즘의 또다른 실시예의 흐름도이다.
본 발명은 RSA 알고리즘을 이용한 보안유지시스템 및 그 방법에 관한 것으로, 보다 상세하게는, RSA 알고리즘을 수행함에 있어 랜덤 계수를 설정함으로써 DPA 공격이 무력화되도록 하는 보안유지시스템 및 그 보안유지방법에 관한 것이다.
최근 수년에 걸쳐, 컴퓨터 및 인터넷 통신망이 거의 완전히 보급됨으로써 전자 메일 서비스, 전자 상거래, 핸드폰을 이용한 무선 통신 및 스마트 카드등의 사용자가 점차 늘어나고 있다. 이러한 기술의 활성화에 있어서, 꼭 해결해야할 기술적인 문제중의 하나가 바로 보안 기술이다. 즉, 안전한 전자 상거래, 메일의 보안 유지, 핸드폰 사용자의 보안 상태 유지등을 위해서는 보내는 메시지의 기밀성과 디지털 서명, 개인 식별, 전자공증, 전자입찰 등의 정보보호 서비스를 제공해야 한다.
특히, 스마트 카드는 현재 기술 수준으로 구현할 수 있는 보안성이 가장 뛰어난 것으로 인정은 되고 있으나, 해킹될 경우 카드에 저장된 개인 신용 정보나 전자 서명 생성키까지도 추출이 가능해 아이씨(IC, 이하 IC라 한다)칩 기반의 본인 인증서, 전자 화폐 등에 대한 위·변조는 물론 개인 정보의 악용까지도 초래할 수 있다. 따라서, 스마트 카드의 보안 시스템에서, 통신 데이터의 암호처리는 필수이며, 현재 가장 많이 이용되고 있는 공개 키 암호로서 RSA 알고리즘을 들 수 있다.
이는 그 발명자인 R.L. Rivest, A. Shamir, L.M. Adleman의 이름을 딴 것으로써, 일반 공개키 암호화 방식에서와 같이 암호화에 쓰이는 일반인도 알 수 있는 공개키와 전자서명에 쓰이는 본인만이 알 수 있는 비밀키를 이용하여 암호화 및 복호화하는 알고리즘이다.
이는, 숫자의 크기가 커질수록 소인수분해가 어렵다는 점에 그 안전도의 기반을 두고 있다. 즉, 메시지를 전송하고자 하는 자는 소수 p, q를 비밀키로 지정하고 N=p*q 인 N값을 공개키로 일반에게 공개한다. 안전을 위하여 p 및 q는 각각 512비트 이상으로 비슷한 길이를 가지는 것이 바람직하다. 그후 Euler totient 함수 φ(n)=(p-1)(q-1) 값과 서로 소의 관계에 있는 임의의 정수 e를 공개키로 지정하고, eㆍd = 1 mod φ(n) 식을 만족하는 d를 비밀키로 지정한다.
즉, 사용자1이 소정의 메시지를 전송하고자 하는 경우, 메시지를 입력하면 이에 대응되는 2진수는 비밀키를 통해서 소정의 암호문으로 작성된다. 이는, C = Md mod N 의 식으로 나타낼 수 있다. 사용자2가 이러한 암호문을 받아서, 메세지를 확인하는 경우는, M = Ce mod N의 식으로 나타낼 수 있다. 이러한 식들에서, C는 암호문, M은 메세지, d는 비밀키, 그리고, e 및 N은 공개키를 나타낸다. 한편, 이와는 반대로, 사용자1이 공개키를 이용하여 소정의 암호문을 작성하고, 사용자2가 자신의 비밀키를 사용하여 암호문을 해독하는 방식도 가능하다.
이러한 멱승(exponentiation) 연산식은 전자 서명을 하는 경우에도 그대로 적용되는데, 즉, 보내는 메시지에 디지털 서명을 하기 위해서 전송자는 S = Md mod N의 과정을 거쳐 생성된 서명문 S와 메시지 M을 수신자에게 전달하며, 수신자는 M` = Semod N의 과정을 거쳐 복호화를 한 후, 수신된 M과 계산된 M`를 비교하여 양자가 같으면 진정한 서명으로 인증을 하게 된다.
이 암호법에서는, 암호화·복호화와 함께, 거듭제곱 잉여 승산 XY mod N을 이용하지만, 이것은 공지(公知)의 설계 알고리즘에 의해 잉여 승산 A2 mod N과 AB mod N의 2개의 형태로 분해할 수 있다. 결국 d = d(n), d(n-1)···d(0)의 값 d(i)를 상위 d(n)에서 최하위의 d(0)까지 순서대로 1비트씩 봐가며, d(i) = 0이면 A2 mod N만을, d(i) = 1이면 A2 mod N과 AB mod N을 연산한다. 따라서, d(i) = 0일 때에는 A2 mod N의 연산 후에 i = 0인가의 판정처리가 행해지고, d(i) = 1일 때에는 A2 mod N과 AB mod N의 연산 후에 i = 0인가의 판정처리가 행해지므로, ei = 0과 1에 대응한 2가지의 전류파형의 형태가 나타난다.
도 1 및 도 2는, 이러한 RSA 알고리즘을 보다 구체적으로 설명하기 위하여 제공된 흐름도로써, RSA 알고리즘 중 특히 비밀키를 이용하여 암호화하는 방식에 대한 흐름도이다. 도 1은 상술한 설명과 같이 비밀키의 상위 비트로부터 하위 비트로 가면서 연산하는 방식이고, 도 2는 이와 반대로 하위 비트로부터 상위 비트로 가면서 연산하는 방식이다.
도 1에 따르면, 사용자1이 메세지를 입력하면, 그 메세지에 대응되는 2진수 M이 변수 R 값으로 입력된다(S 11). 비밀키 d의 비트수가 1024 비트인 경우를 예로 들면, 0 비트 부터 1023비트 까지 존재하고, 최상위 비트(1023번째 비트)는 당연히 1이므로, 그 다음 비트부터 시작하게 된다. 즉, i= n-2에 해당하는 1022번째 비트값부터 시작하게 된다(S 12). 이때, i는 비밀키 d의 비트순서, n은 공개키 N의 비트수를 의미한다.
다음으로, 최초 R값을 이용하여 R= R2 mod N의 멱승 연산식을 수행한다(S 13). 그리고 나서, 비밀키 d의 i번 째 비트값이 1인지를 판단하고(S 14), 1인 경우, R= R2 mod N에서 구해진 R에 M값을 곱한 후, 다시 N으로 나눈 나머지를 새로이 R값으로 결정한다(S 15).
d의 i번 째 비트값이 1이 아니라면, i=0, 즉, 최하위 비트까지 연산되었는지를 다시 판단하여(S 16), 0이 아닌 경우라면 i값을 하나 줄이고 다시 멱승 연산식을 수행한다(S 17, S 13). 최하위 비트까지 연산되었다고 판단되면(S 16), 구해진 R값이 암호문 C로 결정된다(S 18).
한편, 도 2는 비밀키 d의 하위비트부터 상위 비트로 가면서 멱승 연산을 수행하는 흐름도이다. 도 1의 알고리즘과 비교할 때, i=0부터 시작하여(S 22) i값을 하나씩 증가시켜, 최상위비트(i=n-1)까지 연산하는 방식으로 동작한다.
즉, 메세지에 대응되는 2진수 M을 S값으로 두고, R은 임의로 1로 둔 다음(S 21). 최초 i=0 이므로(S 22), d(0)= 1인지를 판단한다(S 23). 즉, 비밀키 d의 0번째 비트값이 1이라면, R값을 R*S mod N으로 두고(S 24), S를 S2 mod N의 식으로 멱승 연산하게 된다(S 25). d(0)=0이라면 R값을 바꾸지 않고 S=S2 mod N 식을 바로 연산하게 된다(S 25).
i값이 최상위 비트에 도달하였는지 판단한 후(S 26), 아직 도달하지 않은 경우라면, i값을 1만큼 증가시킨 후(S 27), 다시 멱승 연산을 수행하고, 최상위 비트에 도달한 경우라면, 이 때의 R값이 암호문으로 정해지게 된다(S 28).
한편, 이러한 RSA 알고리즘에 의해 '스마트카드는 해킹의 안전지대'란 인식이 생길 정도로 어느 정도의 보안성이 인정되어 왔으나, 최근 스마트카드에 대한 기존 해킹 방법과는 양상을 달리하는 물리적 공격(Side Channel Attack) 방법이 등장하면서 이러한 인식이 도전받고 있다.
이러한 물리적 공격의 종류로는, 크게 디캡(decap), 타이밍(timing), 전력분석(DPA), 오류 주입법(Fault Insertion) 등 4가지를 들 수 있다. 디캡 방식은 스마트 카드의 IC 칩을 질산용액에 담가 표면에 그려진 회로를 찾는 것으로 이렇게 찾아낸 회로에 각종 전기 신호를 입력해 비밀키 등 주요 데이터를 얻는 방법이다. 타이밍 공격은 IC 칩의 암호 알고리즘이 비밀키와 관련된 정보를 처리하는데 걸리는 시간과 그렇지 않은 데이터를 처리하는데 걸리는 시간 사이의 차를 분석해 비밀키를 알아내는 방법이다. 오류주입법은 IC 칩에 고의로 잘못된 정보를 입력하고 IC 칩의 반응데이터를 분석하는 방식으로 비밀키를 알아낸다.
한편, 이러한 물리적 공격방법 중 가장 위협적인 방식으로 알려진 전력분석 공격은, 비밀키와 관련된 데이터를 처리할 때 IC 칩이 사용하는 전력량과 그렇지 않을 경우의 전력량을 비교분석하는 방식이다. 즉, CMOS 트랜지스터의 소모전력은 트랜지스터의 상태 전이 및 해밍 웨이트(0이 아닌 비트의 개수: Hamming weight)와 관련이 있다는 관점에서 출발한 공격방법으로, RSA 알고리즘의 멱승 연산식( C = Md mod N )에 있어서, 임의의 암호키를 적용시켜, 메세지 M을 변화시키면서 소비전류 파형을 측정하여 통계를 내게 된다. 즉, 암호키를 여러 가지로 변화시키면서 RSA 알고리즘에 대입하여 중간 결과를 연산하는 과정을 반복하는 경우, 올바른 키일때는 전류파형이 큰 피크가 나타나므로 통계적인 방법으로 이러한 소비 전류 파형을 분석하여 비밀키를 알아내게 된다.
이와 같은 DPA 공격에 대비하기 위하여, 미국특허 US 6,510,518호와 같이 로직데이터가 0 및 1값을 동시에 갖도록 쌍으로 생성 용적을 증가시키거나, 미국 특허 US 5,991,415 호와 같이 중간 데이터의 예측이 불가능하도록 알고리즘을 변형하는 방식등이 종래에 사용되었다.
즉, US 6,510,518에서 제시하는 기술에 따르면, 해밍 웨이트의 분류가 불가능하도록 해밍 웨이트를 두가지 상태 즉, 0 및 1을 동시에 가지도록 변형 시키게 되는데, 이 경우, 용적이 두 배로 증가된다는 문제점이 있다.
한편, 알고리즘을 변형하여 알고리즘의 순서 및 입력값을 변화시키는 방식(US 6,298,135)에 따르면, 상위비트로부터 하위비트로의 연산 및 하위비트로부터 상위비트로의 연산을 병행하거나 혼합하여 연산하므로, 연산속도가 지연되고, 또한, 연산의 후반부는 항상 동일하여 공격자가 어느 정도 예측이 가능하다는 문제점이 있다.
본 발명은 상기와 같은 문제점을 해결하기 위하여 안출된 것으로서, 본 발명에 따르면, 임의로 랜덤 계수를 생성하여 이를 이용하여 암호화 및 복호화를 수행함으로써 DPA 공격시 예측이 불가능한 보안유지시스템 및 방법이 제공된다.
상기 목적을 달성하기 위한 본 발명에 따른 보안유지시스템은, 메시지의 암호화 및 암호문의 복호화 중 어느 하나의 경우에 사용되는 비밀키 및 공개키를 수신하는 키입력부, 소정크기의 비트를 가지는 랜덤계수 r을 생성하는 랜덤계수생성부, 상기 r값을 이용하여 상기 비밀키를 제1비밀키 및 제2비밀키로 분할하고, 각각의 키 및 상기 공개키를 사용하여 RSA 알고리즘의 멱승 연산을 수행하는 제1연산부, 및 상기 제1비밀키 및 상기 제2비밀키를 사용하여 각각 연산된 상기 멱승연산결과를 합성함으로써, 상기 암호화처리 및 복호화처리 중 어느 하나를 수행하는 제2연산부를 포함한다.
바람직하게는, 외부로부터 상기 메시지를 수신하여 대응되는 2진수값으로 변환하여 상기 제1연산부로 출력하는 메시지 입력부, 및 상기 제2연산부에서 처리된 결과를 변환하여, 상기 결과에 대응되는 암호문 및 해독문 중 어느 하나를 출력하는 출력부를 더 포함할 수도 있다.
한편, 상기 제1연산부는, 상기 비밀키에 대하여 상기 랜덤계수값을 감산한 값 및 상기 랜덤계수값을 각각 제1비밀키 및 제2비밀키로 사용하여 비밀키를 분할할 수 있으며, 또는, 상기 비밀키를 랜덤계수값을 기준으로 좌측 및 우측으로 나누고, 각각을 제1비밀키 및 제2비밀키로 사용할 수도 있다.
감산한 경우에는, 제1비밀키로부터 연산된 멱승 연산 결과에 제2비밀키로부터 연산된 멱승 연산 결과를 반영하여 보정함으로써 최종 암호화 및 복호화를 행할 수 있다.
랜덤계수값을 기준으로 좌우로 분할하는 경우, 제1비밀키 및 제2비밀키의 자 리수를 맞추고, 각 비밀키의 대응되는 위치의 비트값에 대응되는 소정 수식에 의해 멱승 연산을 행함으로써 최종 암호화 및 복호화를 행할 수 있다.
한편, 본 발명에 따른 보안유지시스템에서 RSA 알고리즘을 이용한 보안유지방법은, (a) 메시지의 암호화 및 암호문의 복호화 중 어느 하나의 경우에 사용되는 비밀키 및 공개키를 수신하는 단계, (b) 소정크기의 비트를 가지는 랜덤계수 r을 생성하는 단계, (c) 상기 r값을 이용하여 상기 비밀키를 제1비밀키 및 제2비밀키로 분할하고, 각각의 키 및 상기 공개키를 사용하여 RSA 알고리즘의 멱승 연산을 수행하는 단계, 및 (d) 상기 제1비밀키 및 상기 제2비밀키를 사용하여 각각 연산된 상기 멱승연산결과를 합성함으로써, 상기 암호화처리 및 복호화처리 중 어느 하나를 수행하는 단계를 포함한다.
바람직하게는, 외부로부터 상기 메시지를 수신하여 대응되는 2진수값으로 변환하여 출력하는 단계, 및 상기 암호화처리 및 복호화처리 중 어느 하나의 처리결과를 변환하여, 상기 처리결과에 대응되는 암호문 및 해독문 중 어느 하나를 출력하는 단계를 더 포함할 수 있다.
한편, 상기 (c)단계에서는, 상기 비밀키에 대하여 상기 랜덤계수값을 감산한 값 및 상기 랜덤계수값을 각각 제1비밀키 및 제2비밀키로 사용할 수 있으며, 또는, 상기 랜덤계수값을 이용하여 좌측 및 우측으로 나눔으로써 각각 제1비밀키 및 제2비밀키로 사용할 수 있다.
랜덤계수값을 감산하여 비밀키를 분할한 경우에는, 상기 (d)단계에서, 제1비밀키로부터 연산된 멱승 연산 결과에 제2비밀키로부터 연산된 멱승 연산 결과를 반 영하여 보정함으로써 최종 암호화 및 복호화를 행할 수 있고, 랜덤계수값을 기준으로 좌우로 분할하는 경우에는, 소정 수식을 이용하여 제1비밀키 및 제2비밀키의 자리수를 맞추고, 각 비밀키의 대응되는 위치의 비트값에 대응되는 소정 수식에 의해 멱승 연산을 행함으로써 최종 암호화 및 복호화를 행할 수 있다.
이하에서 첨부된 도면을 참조하여 본 발명을 자세하게 설명한다.
도 3은 본 발명에 따른 보안유지시스템의 구성을 간단한 블럭도로 나타낸 도면이다. 도면에 따르면, 본 발명의 보안유지시스템은, 메시지 입력부(200), 키입력부(300) 및 제어부(100)를 포함한다. 제어부(100)는 랜덤계수 생성부(110), 제1연산부(120), 제2연산부(130) 및 출력부(140)를 포함한다.
한편, 상술한 바와 같이 RSA 알고리즘에서는 비밀키를 이용하여 메세지를 전송하고 공개키를 이용하여 이를 확인하는 제1방식 및 공개키를 이용하여 메세지를 전송하고 비밀키를 이용하여 이를 확인하는 제2방식이 모두 가능한데, 두 방식은 연산수식이 정반대일 뿐 연산 방식 및 순서는 동일하므로, 이하에서의 설명은 비밀키를 이용하여 암호화하는 경우에 한정하여 설명한다.
메시지 입력부(200)는 사용자가 전송하고자 하는 메시지를 수신하여 대응되는 2진수 값으로 변환한 후, 제어부(100)로 출력하는 역할을 한다. 즉, 사용자가 소정 문자를 입력하면, 이에 대응되는 디지털 코드로 변환한다. 이하에서는, 변환된 메시지를 M으로 표기한다.
한편, 키입력부(300)는 암호화 및 복호화에 필요한 공개키 및 비밀키를 수신하는 역할을 한다. 상술한 바와 같이, RSA 알고리즘은 공개키 및 비밀키를 이용하 여 멱승 연산 방정식 C=Md mod N 을 통해 메세지를 암호화하고, 다시 M=Ce mod N의 방정식을 통해 암호문을 복호화하는 알고리즘으로써, 비밀키 d 및 공개키 e, N은 메세지를 전송하고자 하는 자 및 해독하고자 하는 자에 의해 직접 입력된다. 키입력부(300)는 이러한 비밀키 및 공개키를 수신하여 대응되는 디지털 코드로 변환한 후, 제어부(100)로 출력하여 제어부(100)로 하여금 RSA 알고리즘 연산을 수행할 수 있도록 한다.
제어부(100)의 세부 구성을 통해, 제어부(100)의 작용에 대하여 설명하면, 먼저, RSA 알고리즘을 통한 암호화가 개시되면, 랜덤계수 생성부(110)는 임의의 계수 r을 생성하여, 제1연산부(120)로 출력한다. 이 때, r의 비트 크기는 임의로 설정할 수 있는 것으로, 그 크기가 크면, 연산량이 늘어나지만 그만큼 보안성을 높일 수 있고, r의 비트크기를 줄이면, 연산량은 줄어들지만 보안성이 떨어지게 되므로, 실험적으로 적당한 크기의 비트수를 가지도록 정한다. 대략 232 보다 작은 r을 생성하면 충분한 안전성을 유지할 수 있다.
제1연산부(120)는, 랜덤계수 r을 이용하여 비밀키를 제1비밀키 및 제2비밀키로 분할하고, 분할된 제1비밀키 및 제2비밀키와 입력된 공개키를 이용하여 멱승연산을 수행한다.
제2연산부(130)는, 제1비밀키 및 제2비밀키에 의해 각각 연산된 멱승연산결과를 이용하여 비밀키 d에 의한 멱승 연산 결과를 추출해내는 작용을 한다. 즉, 제1비밀키 및 제2비밀키로 분할하여 연산한 것에 의한 영향을 보정하여, 비밀키 d 로 암호화 또는 복호화 한 결과와 동일하도록 만드는 연산을 수행한다.
이러한 제1연산부(120) 및 제2연산부(130)의 동작과 관련하여, 본 발명의 일실시예로써, 비밀키 d에 대하여 랜덤계수 r을 감산한 값 d-r을 제1비밀키로 두고, 랜덤계수 r을 제2비밀키로 두고 난 후, 각 비밀키에 대하여 멱승 연산을 수행한 후, 보정하여 암호문을 최종 작성할 수 있다.
도 4에서 이러한 연산작용에 대한 흐름도를 도시하고 있다. 도면에 따르면, 사용자가 메시지 M을 입력하면(S410), 랜덤계수 생성부(110)에서 r값을 임의로 선택한다(S420). 제1연산부(120)는, 선택된 r값을 이용하여, 비밀키를 d-r로 새로이 설정하고(새로 설정된 키를 "제1비밀키"라 함), 이를 이용하여 멱승 연산을 수행한다(S440).
이 경우, 멱승 연산 방정식은 C = Md-r mod N 의 수식으로 표현된다. 이 방정식의 연산은 도 2에 나타난 흐름도와 같이 처리될 수 있다. 한편, 랜덤계수 r을 제2비밀키로 두고, 다시 C'=Mr mod N의 수식을 연산한다(S450). 이러한 수식에 나타나는 계수 C 및 C'는 각각 제1비밀키에 의해 연산된 결과 및 제2비밀키에 의해 연산된 결과를 나타낸다.
제2연산부(130)는, 제1비밀키에 의한 결과 C = Md-r mod N 및 제2비밀키에 의한 결과 C'=Mr mod N를 이용하여 C*C' mod N을 연산함으로써 최종 암호문 C를 추출한다(S460). C*C' mod N의 연산 결과는 암호문 C와 같은 것은 아래의 수식을 통 해 알수 있다.
Figure 112003037611847-pat00001
Figure 112003037611847-pat00002
Figure 112003037611847-pat00003
Figure 112003037611847-pat00004
이와 같은 방식으로 최종 암호문 C를 구할 수 있다.
한편, 본 발명의 또다른 실시예로써, 비밀키 d를 랜덤계수 r을 기준으로 좌우측으로 분할하는 방식으로 처리할 수도 있다. 이에 대해 도 5에서 도시하고 있다. 도면에 따르면, 사용자가 메세지 M을 입력시키면(S510), 랜덤계수 r값을 임의로 선택한다(S520). 이 경우, 공개키 N의 비트크기 n보다 작은 크기의 랜덤계수를 선택한다.
다음으로, 제1연산부(120)가 r값을 기준으로 d(제1비밀키) 및 d'(제2비밀키)로 분할하게 된다(S530). 즉, 원 비밀키 d에서 r의 비트크기에 해당하는 만큼의 하위비트를 제2비밀키(d')로 저장하고, 원 비밀키 d를 r비트만큼 비트별 우측 쉬프트(bitwise right shift)시켜, d'값이 소거된 값을 제1비밀키 d로 저장한다.
그리고 나서, 메세지 M을 r번 제곱하여 M'로 저장함으로써, 제1비밀키 및 제2비밀키의 자리수를 맞추게 된다(S540).
다음으로, 제1비밀키 및 제2비밀키의 비트크기를 맞추는 단계가 진행된다(S550). 즉, r이 n/2 보다 크면 제2비밀키의 비트 크기가 제1비밀키보다 커지게 되므로, 제1비밀키의 상위 2r-n 비트 크기를 0으로 패딩하여 비트크기를 맞추고, r이 n/2보다 작으면 제1비밀키의 비트크기가 제2비밀키보다 커지게 되므로, 제2비밀키의 상위 n-r 비트 크기를 0으로 패딩한다. 따라서, i의 초기치는, r이 n/2보다 작으면 n-r-1이 되고, r이 n/2보다 크면, r-1이 된다.
다음으로, 메세지 M'를 멱승 연산하여 암호문을 작성하는데, 상술한 실시예처럼 도 1및 도 2의 멱승연산을 사용하지 않고, 본 실시예에서는, C=C2 mod N 의 수식을 사용하는 double method를 활용한다. double method란 중간결과를 제곱한 후 제1비밀키의 i번째 비트가 1이면 중간결과에 M'를 곱하고, 제2비밀키의 i번째 비트가 1이면 중간결과에 M을 곱하는 동작을 제1비밀키 및 제2비밀키의 비트수에 해당하는 수만큼 반복루프를 수행하는 방법이다.
즉, 제1비밀키 및 제2비밀키의 자리수 및 비트크기가 맞춰지면, C=C2 mod N 연산을 수행하고(S560), 제1비밀키의 i번째 비트가 1인지 판단한다(S570). 최초 실행시 C의 값은 1로 두고 연산을 수행한다.
제1비밀키의 i번째 비트가 1이면, C*M' mod N 연산을 수행한 후, 그 결과값을 다시 C로 저장한다(S575). 그리고 나서, 제2비밀키의 i번째 비트가 1인지를 판단한 후(S580), 1이라면, C*M mod N 연산을 수행하고 그 값을 다시 C값으로 저장한다(S585).
i값이 0, 즉, 최하위비트까지 도달하였는지 판단하여(S590), 도달한 경우라 면, 그때의 C값이 최종 암호문으로 결정되고(S598), 그렇지 않은 경우라면, 다시 i값을 1만큼 줄이고, 그때의 C값을 C2 mod N식에 대입하여 다시 C값을 결정한 후(S560), 상술한 단계를 반복한다.
한편, 만일 제1비밀키 및 제2비밀키의 i번째 비트값이 모두 1인 경우라면, M*M' mod N를 미리 계산하여 메모리에 저장시켜 놓으면, 곱셈을 한번만 수행하게 되므로, 통계적으로 약 5%정도의 연산량을 더 줄일 수 있다.
한편, 출력부(140)는, 제2연산부(130)에서 최종적으로 얻어진 디지털 코드인 C값을 변환하여 원 메세지 형태로 출력하는 작용을 한다.
도 3에서, 랜덤 계수 생성부(110), 제1연산부(120), 제2연산부(130) 및 출력부(140)등은, 각각 별개의 유닛(unit)인 것처럼 도시되어 있으나, 이는 별개의 칩(chip)을 사용할 수도 있고, 하나의 마이크로프로세서를 통해 구현될 수도 있다.
한편, 본 발명에 따른 RSA 알고리즘 보안유지방법은, 상술한 도 4 및 도 5의 흐름도 및 그에 대한 설명을 통해 나타난다.
즉, 사용자가 메세지를 입력하는 단계, 비밀키 및 공개키를 입력하는 단계, 랜덤계수를 생성하는 단계, 랜덤계수를 이용하여 비밀키를 분할하는 단계, 분할된 비밀키 각각에 대하여 멱승 연산을 수행한 후, 보정하여 최종 암호문을 생성하는 단계를 포함한다.
이 경우, 랜덤계수를 이용하여 비밀키를 분할하는 단계 및 각 비밀키로부터 최종적으로 암호문을 생성하는 단계는, 도 4 및 도 5에 도시된 흐름도에서 나타난 다. 이러한 제1실시예 및 제2실시예에 대한 설명은 상술한 바와 같다.
정리하면, 제1실시예에서는, 랜덤계수 r을 감산한 값 d-r을 제1비밀키로 두고, 랜덤계수 r 자체를 제2비밀키로 둔 채, 각각에 대한 멱승 연산을 수행하여, C 및 C'를 연산한다. 즉, 최종적으로 얻어진 암호문의 해당 비트값을 Ci 라 하면, Ci 는 C*C' mod N의 식에 의해 얻어진다.
한편, 제2실시예는, 랜덤계수 r을 기준으로 비밀키 d에서 r의 비트크기에 해당하는 하위비트를 제2비밀키로 두고, 원 비밀키 d를 r비트만큼 우측으로 쉬프트시켜, 그 값을 제1비밀키로 둔다. 각 비밀키의 비트수를 맞춘 후, double method 방식에 따라 암호문을 추출한다. 한편, M*M' mod N값을 미리 연산하여 메모리에 저장한 경우, 제1비밀키 및 제2비밀키의 해당비트가 모두 1인 경우에 이를 이용함으로써 연산속도 지연을 줄일 수도 있다.
제1실시예 및 제2실시예에 따라서, 랜덤계수 r값을 이용하여 멱승 연산을 수행하면, DPA 공격이 거의 불가능해진다. 따라서, 전자 메일, 전자 서명, 및 인증등을 안전하게 구현할 수 있다.
이상 설명한 바와 같이, 본 발명에 따르면, RSA알고리즘을 이용하는 보안 시스템에 있어서, 랜덤한 값으로 비밀키를 분할한 후, 최종적으로 분할로 인해 발생한 영향을 보정함으로써, DPA와 같은 물리적 공격시 공격자가 중간 연산 과정을 예측할 수 없도록 하여 전자 메일 및 전자 서명등을 안전하게 행할 수 있게 된다. 또 한, 기존에 DPA 공격에 대비하기 위한 RSA 알고리즘과 달리 하드웨어의 변형이 없으며, 연산속도도 크게 느려지지 않는다는 효과도 있다.
또한, 이상에서는 본 발명의 바람직한 실시예에 대하여 도시하고 설명하였지만, 본 발명은 상술한 특정의 실시예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진자에 의해 다양한 변형실시가 가능한 것은 물론이고, 이러한 변형실시들은 본 발명의 기술적 사상이나 전망으로부터 개별적으로 이해되어져서는 안될 것이다.

Claims (20)

  1. 메시지의 암호화 및 암호문의 복호화 중 어느 하나의 경우에 사용되는 비밀키 및 공개키를 수신하는 키입력부;
    상기 비밀키의 비트크기보다 작은 값인 랜덤계수 r을 생성하는 랜덤계수생성부;
    상기 r값에 기초하여 상기 비밀키를 제1비밀키 및 제2비밀키로 분할하고, 상기 제1비밀키 및 상기 제2비밀키 각각과 상기 공개키를 사용하여 RSA 알고리즘의 멱승 연산을 수행하는 제1연산부;및
    상기 제1비밀키 및 상기 제2비밀키를 사용하여 각각 연산된 상기 멱승연산결과를 합성함으로써, 상기 암호화처리 및 복호화처리 중 어느 하나를 수행하는 제2연산부;를 포함하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템.
  2. 제1항에 있어서,
    외부로부터 상기 메시지를 수신하여 대응되는 2진수값 M으로 변환하여 상기 제1연산부로 출력하는 메시지 입력부;및
    상기 제2연산부에서 처리된 결과를 변환하여, 상기 결과에 대응되는 암호문 및 해독문 중 어느 하나를 출력하는 출력부;를 더 포함하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템.
  3. 제1항에 있어서,
    상기 제1연산부는, 아래의 수식을 이용하여 멱승 연산하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템:
    C = Md mod N , M = Ce mod N : 비밀키를 이용하여 암호화하는 경우,
    C = Me mod N , M = Cd mod N : 공개키를 이용하여 암호화하는 경우,
    여기서, C는 암호문, M은 메시지, d는 비밀키, 그리고, e 및 N은 공개키이다.
  4. 삭제
  5. 제3항에 있어서,
    상기 제2연산부는,
    아래의 수식을 이용하여 상기 메세지의 암호화처리 및 복호화처리 중 어느 하나를 수행하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템:
    Ci = C * C' mod N : 암호화처리의 경우,
    Mi = M * M' mod N : 복호화처리의 경우,
    여기서, Ci은 암호문, Mi은 최종 해독된 메시지, C 및 M은 각각 상기 제1비밀키를 사용한 멱승연산결과, 그리고, C' 및 M'는 각각 상기 제2비밀키를 사용한 멱승연산결과이다.
  6. 제1항에 있어서,
    상기 제1연산부는, 상기 랜덤계수 비트크기에 해당하는 상기 비밀키의 하위비트를 제2비밀키로 두고, 상기 비밀키를 상기 랜덤계수 비트크기만큼 우측으로 쉬프트시킨 값을 제1비밀키로 두는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템.
  7. 제6항에 있어서,
    상기 제1연산부는,
    아래의 수식을 이용하여 상기 제1비밀키 및 상기 제2비밀키의 자리수를 맞추는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템:
    M'= M2⌒r mod N,
    여기서, M은 메세지, r은 랜덤계수, N은 공개키, 그리고, M'는 r값을 기준으로 나누어진 제1비밀키 및 제2비밀키의 자리수를 맞추기 위해 변환된 메세지이다.
  8. 제7항에 있어서,
    상기 제1연산부는,
    아래의 수식을 이용하여 상기 멱승 연산을 수행하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템:
    C = C2 mod N : 암호화처리의 경우,
    M = M2 mod N : 복호화처리의 경우,
    여기서, C는 암호문, M은 메세지, 그리고, N은 공개키이다.
  9. 제8항에 있어서,
    상기 제2연산부는,
    상기 제1비밀키의 i번째 비트값이 1이라면 C*M' mod N 을 연산하여 C값으로 저장하고, 상기 제2비밀키의 i번째 비트값이 1이라면, 상기 C값을 C*M mod N식에 대입하여 얻어진 결과를 최종 C값의 i번째 비트값으로 저장하는 것을 특징으로 하는 RSA 알고리즘을 이용한 암호 시스템.
  10. 제9항에 있어서,
    상기 제2연산부는,
    M*M' 및 C*C'중 어느 하나를 계산하여 저장하고, 상기 제1비밀키 및 상기 제2비밀키의 i번째 비트값이 모두 1인 경우, 상기 M*M' 및 C*C' 중 어느 하나를 아래의 수식에 대입하여 암호화 및 복호화 중 어느 하나를 실행하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지시스템:
    Ci=C*M*M' mod N , Mi=M*C*C' mod N,
    여기서, Ci은 암호문, M은 메시지, M'는 M2⌒r mod N식의 연산 결과이다.
  11. (a) 메시지의 암호화 및 암호문의 복호화 중 어느 하나의 경우에 사용되는 비밀키 및 공개키를 수신하는 단계;
    (b) 상기 비밀키의 비트크기보다 작은 값인 랜덤계수 r을 생성하는 단계;
    (c) 상기 r값을 이용하여 상기 비밀키를 제1비밀키 및 제2비밀키로 분할하고, 각각의 키 및 상기 공개키를 사용하여 RSA 알고리즘의 멱승 연산을 수행하는 단계;및
    (d) 상기 제1비밀키 및 상기 제2비밀키를 사용하여 각각 연산된 상기 멱승연산결과를 합성함으로써, 상기 암호화처리 및 복호화처리 중 어느 하나를 수행하는 단계;를 포함하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법.
  12. 제11항에 있어서,
    외부로부터 상기 메시지를 수신하여 대응되는 2진수값으로 변환하여 출력하는 단계;및
    상기 암호화 및 복호화 중 어느 하나의 경우의 처리결과를 변환하여, 상기 처리결과에 대응되는 암호문 및 해독문 중 어느 하나를 출력하는 단계;를 더 포함 하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법.
  13. 제11항에 있어서,
    상기 (c)단계는,
    아래의 수식을 이용하여 상기 멱승 연산을 행하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법:
    C = Md mod N , M = Ce mod N : 비밀키를 이용하여 암호화하는 경우,
    C = Me mod N , M = Cd mod N : 공개키를 이용하여 암호화하는 경우,
    여기서, C는 암호문, M은 메시지, d는 비밀키, 그리고, e 및 N은 공개키이다.
  14. 삭제
  15. 제13항에 있어서,
    상기 (d)단계는,
    아래의 수식을 이용하여 상기 암호문 및 해독문 중 어느 하나를 추출하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법:
    Ci = C * C' mod N ,
    Mi = M * M' mod N ,
    여기서, Ci은 암호문, Mi은 최종 해독된 메시지, C 및 M은 각각 상기 제1비밀키를 사용하여 멱승연산된 암호문 및 해독문, 그리고, C' 및 M'는 각각 상기 제2비밀키를 사용하여 멱승연산된 암호문 및 해독문이다.
  16. 제11항에 있어서,
    상기 (c)단계는,
    상기 r의 비트크기에 해당하는 상기 비밀키의 하위비트를 제2비밀키로 두고, 상기 비밀키를 상기 r의 비트크기만큼 우측으로 쉬프트시킨 값을 제1비밀키로 두는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법.
  17. 제16항에 있어서,
    상기 (c)단계는,
    아래의 수식을 이용하여 비밀키의 비트 자리수를 맞추는 단계;를 더 포함하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법:
    M'= M2⌒r mod N,
    여기서, M은 메세지, r은 랜덤계수, N은 공개키, 그리고, M'는 제1비밀키 및 제2비밀키의 자리수를 맞추기 위해 변환된 메세지이다.
  18. 제17항에 있어서,
    상기 (c)단계는,
    아래의 수식을 이용하여 상기 멱승 연산을 수행하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법:
    C = C2 mod N : 암호화처리의 경우,
    M = M2 mod N : 복호화처리의 경우,
    여기서, C는 암호문, M은 메세지, 그리고, N은 공개키이다.
  19. 제17항에 있어서,
    상기 (d)단계는,
    (d1) 제1비밀키의 i번째 비트값이 1인지 판단하는 단계;
    (d2) 1이라면 C*M' mod N 을 연산하여 C값으로 저장하는 단계;
    (d3) 제2비밀키의 i번째 비트값이 1인지 판단하는 단계;
    (d4) 1이라면, 상기 C값을 C*M mod N식에 대입하여 얻어진 결과를 최종 C값으로 저장하는 단계;
    (d5) i가 0인지 판단하는 단계;및
    (d6) i가 0이 아니라면, 1을 감산한 후 다시 상기 (c)단계의 멱승 연산을 수행하는 단계;를 포함하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법.
  20. 제18항에 있어서,
    M*M' 및 C*C'를 계산하여 저장하는 단계;를 더 포함하며,
    상기 제1비밀키 및 상기 제2비밀키의 i번째 비트값이 모두 1인 경우, 상기 M*M' 및 C*C'값을 아래의 수식에 대입하여 암호화 및 복호화 중 어느 하나를 실행하는 것을 특징으로 하는 RSA 알고리즘을 이용한 보안유지방법:
    Ci=C*M*M' mod N, Mi=M*C*C' mod N,
    여기서, Ci은 암호문, M은 메시지, M'는 M2⌒r mod N식의 연산 결과이다.
KR1020030070103A 2003-10-09 2003-10-09 Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법 KR100720726B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020030070103A KR100720726B1 (ko) 2003-10-09 2003-10-09 Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법
US10/959,993 US7421074B2 (en) 2003-10-09 2004-10-08 Security system using RSA algorithm and method thereof

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020030070103A KR100720726B1 (ko) 2003-10-09 2003-10-09 Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법

Publications (2)

Publication Number Publication Date
KR20050034238A KR20050034238A (ko) 2005-04-14
KR100720726B1 true KR100720726B1 (ko) 2007-05-22

Family

ID=34420557

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020030070103A KR100720726B1 (ko) 2003-10-09 2003-10-09 Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법

Country Status (2)

Country Link
US (1) US7421074B2 (ko)
KR (1) KR100720726B1 (ko)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2010053319A2 (ko) * 2008-11-06 2010-05-14 삼성전자 주식회사 보안 키 교환 장치 및 방법과 이에 관한 시스템
KR101513012B1 (ko) * 2013-12-19 2015-04-17 호서대학교 산학협력단 오류 주입과 전력 분석을 조합한 공격에 강인한 멱승 방법

Families Citing this family (31)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7092523B2 (en) * 1999-01-11 2006-08-15 Certicom Corp. Method and apparatus for minimizing differential power attacks on processors
US7599491B2 (en) * 1999-01-11 2009-10-06 Certicom Corp. Method for strengthening the implementation of ECDSA against power analysis
KR100564599B1 (ko) * 2003-12-24 2006-03-29 삼성전자주식회사 역원 계산 회로, 역원계산 방법 및 상기 역원계산 방법을실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수있는 기록매체
KR20060081847A (ko) * 2005-01-10 2006-07-13 삼성전자주식회사 비밀키를 보호하는 스마트 카드 및 그것의 방법
EP2395424B1 (en) 2005-01-18 2013-07-31 Certicom Corp. Accelerated verification of digital signatures and public keys
US8467535B2 (en) * 2005-01-18 2013-06-18 Certicom Corp. Accelerated verification of digital signatures and public keys
US20070071243A1 (en) * 2005-09-23 2007-03-29 Microsoft Corporation Key validation service
US20100208894A1 (en) * 2006-09-29 2010-08-19 Linx Technologies, Inc. Encoder and decoder apparatus and methods
KR100937869B1 (ko) * 2006-12-05 2010-01-21 한국전자통신연구원 단순전력분석에 안전한 ＵｎｓｉｇｎｅｄＬｅｆｔ－ｔｏ－Ｒｉｇｈｔ 리코딩 방법 및 통합된 지수승알고리즘 방법
US8050403B2 (en) * 2007-03-06 2011-11-01 Research In Motion Limited Method and apparatus for generating a public key in a manner that counters power analysis attacks
CA2680054C (en) * 2007-03-06 2015-07-07 Research In Motion Limited Method and apparatus for performing elliptic curve scalar multiplication in a manner that counters power analysis attacks
US8391479B2 (en) * 2007-03-07 2013-03-05 Research In Motion Limited Combining interleaving with fixed-sequence windowing in an elliptic curve scalar multiplication
JP5365624B2 (ja) * 2008-03-31 2013-12-11 富士通株式会社 電力解析攻撃への対策機能を備えた復号装置、プログラム、及び復装置を組み込んだ組込機器装置
US8311222B2 (en) * 2008-08-26 2012-11-13 GlobalFoundries, Inc. Hardware based multi-dimensional encryption
GB2479871A (en) * 2010-04-26 2011-11-02 David Coyne System for preventing side channel attacks on a synchronous logic device.
KR101344402B1 (ko) * 2010-08-12 2013-12-26 한국전자통신연구원 Ｒｓａ 서명 방법 및 장치
US8745376B2 (en) 2011-10-14 2014-06-03 Certicom Corp. Verifying implicit certificates and digital signatures
WO2014066610A2 (en) * 2012-10-24 2014-05-01 Holyfield Brian Methods and systems for the secure exchange of information
US10078968B2 (en) * 2012-12-19 2018-09-18 Law School Admission Council, Inc. System and method for electronic test delivery
FR3018372B1 (fr) * 2014-03-06 2023-09-29 Oberthur Technologies Generation de message pour test de generation de cles cryptographiques
KR102399665B1 (ko) 2015-09-11 2022-05-19 삼성전자주식회사 전자 장치의 근접 인증 방법 및 그 장치
FR3055436A1 (fr) * 2016-08-23 2018-03-02 Stmicroelectronics (Rousset) Sas Protection d'un calcul modulaire
FR3055437A1 (fr) 2016-08-23 2018-03-02 Stmicroelectronics (Rousset) Sas Protection d'un calcul d'exponentiation modulaire
FR3069671A1 (fr) 2017-07-25 2019-02-01 Stmicroelectronics (Rousset) Sas Protection d'un calcul iteratif contre des attaques horizontales
CN107483191B (zh) * 2017-08-16 2020-04-14 浪潮集团有限公司 一种sm2算法密钥分割签名系统及方法
CN108055128B (zh) * 2017-12-18 2021-11-19 数安时代科技股份有限公司 Rsa密钥的生成方法、装置、存储介质及计算机设备
EP3579493A1 (fr) 2018-06-08 2019-12-11 STMicroelectronics (Rousset) SAS Protection d'un calcul itératif
EP3579492A1 (fr) 2018-06-08 2019-12-11 STMicroelectronics (Rousset) SAS Protection d'un calcul itératif
FR3094522B1 (fr) 2019-03-29 2021-11-19 St Microelectronics Rousset Protection d’un calcul itératif
KR102348797B1 (ko) 2019-12-04 2022-01-07 한밭대학교 산학협력단 Rsa 암호화 시스템의 rsa 회로 모듈
US11816228B2 (en) 2020-09-25 2023-11-14 Advanced Micro Devices, Inc. Metadata tweak for channel encryption differentiation

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5588061A (en) * 1994-07-20 1996-12-24 Bell Atlantic Network Services, Inc. System and method for identity verification, forming joint signatures and session key agreement in an RSA public cryptosystem
US5768389A (en) * 1995-06-21 1998-06-16 Nippon Telegraph And Telephone Corporation Method and system for generation and management of secret key of public key cryptosystem
US6731755B1 (en) * 1997-07-28 2004-05-04 The Director, Government Communications Headquarters Split-key cryptographic system and method
RU2153191C2 (ru) * 1998-09-29 2000-07-20 Закрытое акционерное общество "Алкорсофт" Способ изготовления вслепую цифровой rsa-подписи и устройство для его реализации (варианты)
JP3926532B2 (ja) * 2000-03-16 2007-06-06 株式会社日立製作所 情報処理装置、情報処理方法、及びカード部材
JP4199937B2 (ja) * 2001-03-06 2008-12-24 株式会社日立製作所 耐タンパー暗号処理方法
JP4188571B2 (ja) * 2001-03-30 2008-11-26 株式会社日立製作所 情報処理装置の演算方法および耐タンパ演算攪乱実装方式

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
[논문] G. Tsudik, "Weak forward Security in Mediated RSA", 2002 Security in Computer Networks Conference(SCN '02)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2010053319A2 (ko) * 2008-11-06 2010-05-14 삼성전자 주식회사 보안 키 교환 장치 및 방법과 이에 관한 시스템
WO2010053319A3 (ko) * 2008-11-06 2010-07-29 삼성전자 주식회사 보안 키 교환 장치 및 방법과 이에 관한 시스템
US8380992B2 (en) 2008-11-06 2013-02-19 Samsung Electronics Co., Ltd. Device and method for security key exchange and system pertaining to same
KR101513012B1 (ko) * 2013-12-19 2015-04-17 호서대학교 산학협력단 오류 주입과 전력 분석을 조합한 공격에 강인한 멱승 방법

Also Published As

Publication number Publication date
US20050078821A1 (en) 2005-04-14
US7421074B2 (en) 2008-09-02
KR20050034238A (ko) 2005-04-14

Similar Documents

Publication Publication Date Title
KR100720726B1 (ko) Ｒｓａ 알고리즘을 이용한 보안유지시스템 및 그 방법
US4964164A (en) RSA computation method for efficient batch processing
Young et al. The prevalence of kleptographic attacks on discrete-log based cryptosystems
JP4086503B2 (ja) 暗号演算装置及び方法並びにプログラム
US20080240443A1 (en) Method and apparatus for securely processing secret data
US7054444B1 (en) Public and private key cryptographic method
KR20020025630A (ko) 비밀 정보의 처리 장치, 프로그램 또는 시스템
NZ550786A (en) Computationally asymmetric cryptographic systems
EP1330702B1 (en) Method and system of using an insecure crypto-accelerator
EP2742644B1 (en) Encryption and decryption method
WO2018125677A1 (en) Key processing method and device
JP2004304800A (ja) データ処理装置におけるサイドチャネル攻撃防止
Borst et al. Cryptography on smart cards
US7123717B1 (en) Countermeasure method in an electronic component which uses an RSA-type public key cryptographic algorithm
US9419789B2 (en) Method and apparatus for scalar multiplication secure against differential power attacks
Paar et al. The RSA cryptosystem
US7158636B2 (en) Multivariable cryptosystem
EP3188000A1 (en) System and method for hiding a cryptographic secret using expansion
CN1985458B (zh) 增强的自然蒙哥马利指数掩蔽和恢复的方法和装置
CN105049208B (zh) 基于双重困难的数据加密方法
KR20090080842A (ko) Ｃｒｔ-ｒｓａ 모듈라 지수승 알고리즘을 이용한 디지털서명 방법, 그 장치 및 이를 기록한 컴퓨터 판독가능 저장매체
CN110299992A (zh) 基于滑动窗口的多变量二次方程的乱序加密方法及装置
Lone et al. Common attacks on RSA and its variants with possible countermeasures
Ghadi A STUDY ON MODIFIED RSA CRYPTOSYSTEM
Yuvarani et al. An Enhanced Multi-Key Asymmetric Cryptosystem for Strengthened Data Security

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20031009

PA0201 Request for examination
PG1501 Laying open of application
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20050923

Patent event code: PE09021S01D

AMND Amendment
E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20060117

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 20050923

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I

J201 Request for trial against refusal decision
PJ0201 Trial against decision of rejection

Patent event date: 20060215

Comment text: Request for Trial against Decision on Refusal

Patent event code: PJ02012R01D

Patent event date: 20060117

Comment text: Decision to Refuse Application

Patent event code: PJ02011S01I

Appeal kind category: Appeal against decision to decline refusal

Decision date: 20070420

Appeal identifier: 2006101001332

Request date: 20060215

AMND Amendment
PB0901 Examination by re-examination before a trial

Comment text: Amendment to Specification, etc.

Patent event date: 20060313

Patent event code: PB09011R02I

Comment text: Request for Trial against Decision on Refusal

Patent event date: 20060215

Patent event code: PB09011R01I

Comment text: Amendment to Specification, etc.

Patent event date: 20051123

Patent event code: PB09011R02I

E801 Decision on dismissal of amendment
PE0801 Dismissal of amendment

Patent event code: PE08012E01D

Comment text: Decision on Dismissal of Amendment

Patent event date: 20060331

Patent event code: PE08011R01I

Comment text: Amendment to Specification, etc.

Patent event date: 20060313

Patent event code: PE08011R01I

Comment text: Amendment to Specification, etc.

Patent event date: 20051123

B601 Maintenance of original decision after re-examination before a trial
PB0601 Maintenance of original decision after re-examination before a trial
J301 Trial decision

Free format text: TRIAL DECISION FOR APPEAL AGAINST DECISION TO DECLINE REFUSAL REQUESTED 20060215

Effective date: 20070420

PJ1301 Trial decision

Patent event code: PJ13011S01D

Patent event date: 20070420

Comment text: Trial Decision on Objection to Decision on Refusal

Appeal kind category: Appeal against decision to decline refusal

Request date: 20060215

Decision date: 20070420

Appeal identifier: 2006101001332

PS0901 Examination by remand of revocation
S901 Examination by remand of revocation
GRNO Decision to grant (after opposition)
PS0701 Decision of registration after remand of revocation

Patent event date: 20070504

Patent event code: PS07012S01D

Comment text: Decision to Grant Registration

Patent event date: 20070424

Patent event code: PS07011S01I

Comment text: Notice of Trial Decision (Remand of Revocation)

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20070515

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20070516

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
G170 Re-publication after modification of scope of protection [patent]
PG1701 Publication of correction
LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee