| 1 |
1
R 및 N이 항상 홀수 이고, R은 2의 멱수라는 입력 값의 특성을 이용하여 확장 이진 GCD 알고리즘에서 뺄셈연산 과정을 제거하는 단계; 및상기 확장 이진 GCD 알고리즘의 결과에 대하여 RSA 용 몽고메리 알고리즘을 적용하여 을 구하는 단계 를 포함하는 몽고메리 알고리즘 파라미터 계산 방법
|
| 2 |
2
제1항에 있어서, 확장 유클리디안 알고리즘을 적용하여 을 만족하는 및 을 구하는 단계; 및 확장 이진 GCD 알고리즘을 적용하여 확장 유클리디안 알고리즘에서 나눗셈 과정을 제거하고, 덧셈, 뺄셈 및 쉬프트 연산만을 이용하여 및 을 구하는 단계 를 더 포함하는 몽고메리 알고리즘 파라미터 계산 방법
|
| 3 |
3
제2항에 있어서, 상기 확장 유클리디안 알고리즘을 적용하여 을 만족하는 및 을 구하는 단계는, 및 의 두 식에서 의 부호가 반대이므로 실제 이 음수가 나올 경우 양수로 처리하고 양수일 경우 음수를 취하고, 모듈러 연산에서 음수는 나오지 않으므로 음수를 취한 후 을 더하여 원하는 값을 구하는 몽고메리 알고리즘 파라미터 계산 방법
|
| 4 |
4
제2항에 있어서, 상기 확장 이진 GCD 알고리즘을 적용하여 상기 확장 유클리디안 알고리즘에서 나눗셈 과정을 제거하고, 덧셈, 뺄셈 및 쉬프트 연산만을 이용하여 및 을 구하는 단계는, 확장 이진 GCD 알고리즘은 3개의 덧셈기와 3개의 뺄셈기, 3개의 쉬프터가 사용되고, 9개의 레지스터가 포함되며, 확장 이진 GCD 알고리즘을 적용하여 구한 변수들의 관계식은 하기 식과 같은 몽고메리 알고리즘 파라미터 계산 방법
|
| 5 |
5
제1항에 있어서, 상기 및 이 항상 홀수 이고, 은 2의 멱수라는 입력 값의 특성을 이용하여 상기 확장 이진 GCD 알고리즘에서 뺄셈연산 과정을 제거하는 단계는, 는 항상 음수이고, 의 연산은 기존의 에서 을 빼는 뺄셈을 진행하게 되므로, 덧셈을 수행하고 앞에 음수를 붙이며, 값이 음수이면 양수로 취하면 되므로 덧셈으로 진행하는몽고메리 알고리즘 파라미터 계산 방법
|
| 6 |
6
제1항에 있어서, 상기 확장 이진 GCD 알고리즘의 결과에 대하여 RSA 용 몽고메리 알고리즘을 적용하여 을 구하는 단계는, 초기 입력 값인 이 항상 홀수이기 때문에 를 구하는 과정을 필요로 하지 않고, 만 있어도 원하는 값을 얻을 수 있기 때문에 와 값은 필요로 하지 않으며, 은 루프 카운터 역할을 하는 숫자이기 때문에 연산을 필요로 하지 않는몽고메리 알고리즘 파라미터 계산 방법
|
| 7 |
7
제1항에 있어서, 상기 확장 이진 GCD 알고리즘의 결과에 대하여 RSA 용 몽고메리 알고리즘을 적용하여 을 구하는 단계는,2개의 덧셈기, 2개의 쉬프터, 2개의 레지스터 및 1개의 카운터만을 필요로 하는 몽고메리 알고리즘 파라미터 계산 방법
|
| 8 |
8
제1항에 있어서, 상기 확장 이진 GCD 알고리즘의 결과에 대하여 RSA 용 몽고메리 알고리즘을 적용하여 을 구하는 단계는, 의 최하위 비트 값부터 구하고, 32회의 루프만 수행하며, 1개의 덧셈기, 1개의 쉬프터, 1개의 레지스터, 1개의 카운터만을 필요로 하는 몽고메리 알고리즘 파라미터 계산 방법
|
