Описание алгоритма шифрования
RSA (от фамилий создателей: Rivest, Shamir и Adeleman) – криптографический алгоритм с открытым ключом, основывающийся на сложности задачи факторизации двух больших простых чисел. Для шифрования применяется операция возведения в степень по модулю большого числа. Для расшифровывания необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители.
Блок-схема алгоритма шифрования
Перед началом работы алгоритма необходимо сгенерировать ключи.
Генерация открытого и секретного ключей
Выбираем два различных простых числа p и q заданного размера (например 1024 бита).
Вычисляем модуль n = p * q.
Вычисляем значение функции Эйлера от числа n: m(n) = (p – 1)(q – 1).
Выбираем целое число e (1 < e < m(n)), взаимно простое с m. Обычно берутся числа Ферма.
Вычисляем число d, удовлетворяющее условию (d * e) mod m = 1.
Пара {e, n} является открытым RSA-ключом.
Пара {d, n} является закрытым RSA-ключом.
Шифрование
Посимвольно шифруем сообщение, пользуясь выражением
Расшифровывание
Обратная операция реализуется выражением
Рисунок 5 - Процесс шифрования и расшифровывания
Текст программы
//
// RSA.h
// RC5
//
// Created by Александр Селиванов on 16.01.2018.
// Copyright © 2018 Alexander Selivanov. All rights reserved.
//
#import <Foundation/Foundation.h>
typedef unsigned long long ulong;
@interface RSA : NSObject
+ (BOOL)isPrime:(ulong)value;
+ (void)generateKeysFromP:(ulong)p andQ:(ulong)q toPubE:(ulong *)e toPrivD:(ulong *)d toModuleN:(ulong *)n;
|
|
|
+ (NSString *)encodeText:(NSString *)string withE:(NSDecimalNumber *)e andN:(NSDecimalNumber *)n;
+ (NSString *)decodeText:(NSString *)string withD:(NSDecimalNumber *)d andN:(NSDecimalNumber *)n;
@end
//
// RSA.m
// RC5
//
// Created by Александр Селиванов on 16.01.2018.
// Copyright © 2018 Alexander Selivanov. All rights reserved.
//
#import "RSA.h"
#include "gmp.h"
@implementation RSA
#pragma mark - utilities
+ (NSDecimalNumber *)remainderOnDividing:(NSDecimalNumber *)dividend by:(NSDecimalNumber *)divisor {
NSDecimalNumber *quotient = [dividend decimalNumberByDividingBy:divisor
withBehavior:[NSDecimalNumberHandler decimalNumberHandlerWithRoundingMode:NSRoundDown scale:0 raiseOnExactness:NO raiseOnOverflow:NO raiseOnUnderflow:NO raiseOnDivideByZero:NO]];
NSDecimalNumber *subtractAmount = [quotient decimalNumberByMultiplyingBy:divisor];
NSDecimalNumber *remainder = [dividend decimalNumberBySubtracting:subtractAmount];
return remainder;
}
#pragma mark - key generation
+ (BOOL)isPrime:(ulong)value {
if (value < 2) {
return false;
}
if (value == 2) {
return true;
}
for (ulong i = 3; i < value; ++i) {
if (value % i == 0) {
return false;
}
}
return YES;
}
+ (ulong)calculateFermatNumber:(ulong)n {
return powl(2, powl(2, n)) + 1;
}
+ (ulong)calculateEwithM:(ulong)m {
ulong n = arc4random() % 5;
ulong e = [self calculateFermatNumber:n++];
for (ulong i = 2; i <= e; ++i) {
if ((e % i == 0) && (m % i == 0)) {
e = [self calculateFermatNumber:n++];
i = 1;
}
}
if (e >= m) {
e = m - 1;
for (ulong i = 2; i <= e; ++i) {
if ((e % i == 0) && (m % i == 0)) {
e--;
i = 1;
}
}
}
return e;
}
+ (ulong)calculateDwithE:(ulong)e andM:(ulong)m {
|
|
|
ulong d = 1;
do {
if (d != e && ((d * e) % m) == 1) {
return d;
} else {
d++;
}
} while (true);
}
+ (void)generateKeysFromP:(ulong)p andQ:(ulong)q toPubE:(ulong *)e toPrivD:(ulong *)d toModuleN:(ulong *)n {
*n = p * q;
ulong m = (p - 1) * (q - 1);
*e = [self calculateEwithM:m];
*d = [self calculateDwithE:*e andM:m];
}
#pragma mark - encoding
+ (NSString *)rsaEncodeCharacter:(mpz_t)ch withE:(mpz_t)e andN:(mpz_t)n {
mpz_t enc;
mpz_init(enc);
mpz_powm(enc, ch, e, n);
char *out_str = mpz_get_str(NULL, 10, enc);
NSString *res = [NSString stringWithUTF8String:out_str];
mpz_clear(enc);
return res;
}
+ (NSString *)encodeText:(NSString *)string withE:(NSDecimalNumber *)e andN:(NSDecimalNumber *)n {
NSString *res = @"";
for (NSUInteger i = 0; i < [string length]; ++i)
{
mpz_t c_m, e_m, n_m;
mpz_init(c_m);
mpz_init(e_m);
mpz_init(n_m);
mpz_set_ui(c_m, [string characterAtIndex:i]);
mpz_set_ui(e_m, [e unsignedIntValue]);
mpz_set_ui(n_m, [n unsignedIntValue]);
NSString *encodedCharacter = [self rsaEncodeCharacter:c_m withE:e_m andN:n_m];
mpz_clear(n_m);
mpz_clear(e_m);
mpz_clear(c_m);
res = [res stringByAppendingFormat: @"%@ ", encodedCharacter];
}
return [res stringByTrimmingCharactersInSet: [NSCharacterSet whitespaceCharacterSet]];
}
#pragma mark - decoding
+ (NSString *)rsaDecodeCharacter:(mpz_t)ch withD:(mpz_t)d andN:(mpz_t)n {
mpz_t dec;
mpz_init(dec);
mpz_powm(dec, ch, d, n);
unichar out_str = (unichar)mpz_get_ui(dec);
NSString *res = [NSString stringWithCharacters:&out_str length:1];
mpz_clear(dec);
return res;
}
+ (NSString *)decodeText:(NSString *)string withD:(NSDecimalNumber *)d andN:(NSDecimalNumber *)n {
NSString *res = @"";
mpz_t d_m;
mpz_t n_m;
mpz_init(d_m);
mpz_init(n_m);
|
|
|
mpz_set_ui(d_m, [d unsignedIntValue]);
mpz_set_ui(n_m, [n unsignedIntValue]);
NSArray *arrayOfChars = [string componentsSeparatedByString:@" "];
for (NSString *obj in arrayOfChars) {
mpz_t c_m;
mpz_init(c_m);
mpz_set_ui(c_m, [obj integerValue]);
NSString *str = [self rsaDecodeCharacter:c_m withD:d_m andN:n_m];
mpz_clear(c_m);
res = [res stringByAppendingString:str];
}
mpz_clear(n_m);
mpz_clear(d_m);
return res;
}
@end
Результат работы программы
Операция генерации ключей при большой размерности операндов занимает значительное время (в данном случае 20.445 сек.), но ключи генерируются гораздо реже выполнения операций шифрования, расшифровывания.
Длина зашифрованного сообщения меньше длины сообщения, зашифрованного алгоритмом RC5, т.к. мы не переводим его в ASCII. Если бы это было реализовано, то длины сообщений совпали бы.
Среднее время шифрования составляет 0.305 сек.
Среднее время выполнения операции расшифровывания составляет 0.0354 сек.
Заключение
Процессы шифрования и дешифрования алгоритма RC5 выполняются за практически одинаковое время, т.к. они выполняются одинаковыми операциями.
Операция генерации ключей алгоритма RSA занимает намного более продолжительное время нежели операции шифрования и дешифрования. Её можно ускорить применив, например, алгоритм решета Эратосфена.
|
|
|
В целом ассиметричный алгоритм более медленный нежели симметричный, т.к. в RSA выполняются «тяжёлые» операции возведения в большую степень.
Дата добавления: 2021-06-02; просмотров: 53; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!