Минимальная реализация алгоритма RSA на C++

06/06/2019 by Андрей Зиновьев

Описание программы

Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов.
Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а затем шифруют сообщение с помощью какого-либо симметрического алгоритма, например AES.
О самом алгоритме можно почитать например тут.
RSA может шифровать числа до так называемого модуля, который является частью ключа. В настоящее время используются модули длиной в 1024, 2048 и даже 4096 бит. В нашей реализации без длинной арифметики получится иметь дело максимум с 64-битными ключами, однако для наглядности этого хватит. Для того, чтобы сообщение при шифровании многократно не увеличивалось в размере, шифровать его надо блоками по $k — 1$ бит, где $k$ — битность ключа. При этом каждый блок перейдет в $k$-битное число, то есть на больших файлах прирост размера составит всего лишь $\frac{k}{k-1}$ раз, и чем больше ключ — тем меньше этот прирост.
В программе делением массива чисел одной битности на числа другой битности занимается функция resize, дополняя недостающие биты нулями.
Шифрованием и одновременно дешифрованием занимается функция process_bytes, так как в RSA оба этих процесса имеют идентичные алгоритмы, отличающиеся только размером блока входа и выхода. Для этого используется алгоритм быстрого возведения в степень.
Также программа может генерировать ключи на основании предустановленных простых чисел (в будущем случайных), или на основании простых чисел, введенных пользователем. Для этого используется нахождении обратного в кольце по модулю расширенным алгоритмом Евклида.
Программа реализована в интерактивном виде, список команд можно вызвать командой h.

Continue reading →

Related Images:

e-olymp 4752. Кинотеатр

21/05/2019 by Андрей Зиновьев

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.

Выходные данные:
Выведите одно число — количество учеников, которые в результате пересадки останутся сидеть на тех же местах.

Тесты

Входные данные	Вывод программы
3 3	3
3 2	2
231 543	3

Continue reading →

Related Images:

e-olymp 8529. Преобразование Капрекара

29/11/2018 by Кирилл Веремйов

Задача

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.

Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.

Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.

Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$

Входные данные

Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).

Выходные данные

Выведите $K(x)$.

Тесты

Входные данные	Выходные данные
100	099
1000000000	0999999999
2414	3177
6174	6174
5	0
7272	5445
142857	750843
495	495
55	00
56	09
554	099
12345	41976

Решение

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	long long x, K = 0, xm = 0, xM = 0;
	//Вводимое число, искомое число, максимальное и минимальное из комбинации цифр
	cin >> x;
	int N[11];
	int n = 0;
	
	while(x != 0){//Количество цифр в числе, запись их в массив цифр
		N[n] = abs(x % 10);
		n++;
		x /= 10;
	}
	
	bool t = true;

	sort(N , N+n);//Сортировка цифр по возрастанию

	long long ten = 1;
	
	for(int j = 0; j < n-1; j++){
		ten *= 10;
	}
	
	long long ten_copy = ten;
	
	for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число
		xm += N[i] * ten;
		ten /= 10;
	}
	
	for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число
		xM += N[i] * ten_copy;
		ten_copy /= 10;
	}
	
	K = xM - xm;
	int c = 0;
	
	long long K_tmp = K;
	//Проверка на равенство количества цифр исходного числа и числа K
	while(K_tmp != 0){
		c++;
		K_tmp /= 10;
	}
	
	//Добавление недостающих ведущих нулей
	for(int i = 0; i < n-c; i++) cout << 0;
	
	if(K!=0)//Если K==0, то нули были выведены предыдущим циклом
		cout << K;//Вывод числа K
		
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long x, K = 0, xm = 0, xM = 0;

//Вводимое число, искомое число, максимальное и минимальное из комбинации цифр

cin >> x;

int N[11];

int n = 0;

while(x != 0){//Количество цифр в числе, запись их в массив цифр

N[n] = abs(x % 10);

n++;

x /= 10;

}

bool t = true;

sort(N , N+n);//Сортировка цифр по возрастанию

long long ten = 1;

for(int j = 0; j < n-1; j++){

ten *= 10;

}

long long ten_copy = ten;

for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число

xm += N[i] * ten;

ten /= 10;

}

for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число

xM += N[i] * ten_copy;

ten_copy /= 10;

}

K = xM - xm;

int c = 0;

long long K_tmp = K;

//Проверка на равенство количества цифр исходного числа и числа K

while(K_tmp != 0){

c++;

K_tmp /= 10;

}

//Добавление недостающих ведущих нулей

for(int i = 0; i < n-c; i++) cout << 0;

if(K!=0)//Если K==0, то нули были выведены предыдущим циклом

cout << K;//Вывод числа K

return 0;

}

Объяснение

Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.

Код на ideone
Зачтено на e-olymp

Related Images:

e-olymp 8522. Делимость

17/10/2018 by Андрей Зиновьев

Задача

Заданы два натуральных числа $a$ и $b$. Проверьте, делится ли $a$ на $b$.

Входные данные: Два натуральных числа $a$ и $b$ $(1 \le a, b \le 10^9)$

Выходные данные: Если $a$ не делится на $b$ нацело, вывести в одной строке частное и остаток от деления $a$ на $b$. Иначе вывести "Divisible".

Тесты

$a$	$b$	Вывод программы
15	3	Divisible
12	7	1 5
15	23	0 15
1000000000	889879	1123 665883

Continue reading →

Related Images:

e-olymp 97. Числа Белла

23/05/2018 by Томас Пасенченко

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Входные данные

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

Выходные данные

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные	Выходные данные
1 5 3 2 4 2 4 3 10000 3	0 2 5 2 24962375
18 2 465 1009 9998 9221 548 11	134 0 778 14412
1093 1093 1103 1723 3931 617 4868 6113 9534 71	1 0 10635 0 639989
617 17 42 11 0 5	11295 63 0

Код программы

#include <iostream>
using namespace std;

int main() {
    // Числа Белла
    int n, p;
    while (cin >> n >> p) {
        int k = 0;
        for (int i = 1; i <= n; i++) {
            int fact = i;
            while (fact) {
                fact /= p;
                k += fact;
            }
        }
        cout << k << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

// Числа Белла

int n, p;

while (cin >> n >> p) {

int k = 0;

for (int i = 1; i <= n; i++) {

int fact = i;

while (fact) {

fact /= p;

k += fact;

}

cout << k << "\n";

}

return 0;

}

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

Related Images:

I. Новорічні іграшки

29/04/2015 by Іванов Вячеслав Володимирович

Задача с SEERC 2015, [latex]\frac {1}{8}[/latex] финала.

Формулировка

«У кожного свята є один недолік – рано чи пізно, але воно закінчується. Ось і новорічні свята завершились і малому Дмитрику необхідно скласти іграшки у коробки. Частину іграшок він склав у одну коробку, а частину у іншу. Старший брат Дмитрика Петрик навчається в математичному класі. І його цікавить чи можна перекласти всі іграшки у одну з коробок (кожна коробка вміщує усі іграшки), якщо з одної коробки у іншу можна перекладати стільки іграшок, скільки у іншій коробці.

Вхідні дані:
Два числа N і M — кількість іграшок у першій та другій коробці (1 ≤ N, М ≤ 2000000000).
Вихідні дані:
Bиведіть 1 – якщо можна перекласти іграшки у одну коробку, або 0 – якщо такої можливості немає.»

Алгоритм

Ограничение на входные данные.
Предположим, что при некоторых [latex]N[/latex], [latex]M[/latex] ответ положительный. Пусть [latex]c = N + M[/latex].
Будем выстраивать последовательность шагов от конца к началу. Стартовая позиция — [latex]\left(c \quad 0 \right)[/latex](подарков в коробках). Очевидно, что прийти в неё можно только из [latex]\left( \frac {c}{2} \quad \frac {c}{2} \right)[/latex]. Определим вид предыдущей позиции: [latex]\begin{cases} a+b=c, \\ a-b=\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} 2a=c+\frac { c }{ 4 } , \\ b=a-\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} a=\frac { 3c }{ 4 } , \\ b=\frac { c }{ 4 } ; \end{cases}[/latex]. Принципиально важно, что показатель знаменателя на каждом шаге монотонно возрастает. В силу конечности [latex]c[/latex], процесс конечен. Меньший член пары имеет общий вид [latex]\frac {c}{2^{n}}[/latex], следовательно, [latex]c = N + M = 2k[/latex] (здесь и далее предполагается, что все переменные — некоторые натуральные числа).
Заметим, что постоянный множитель [latex]k[/latex] не влияет на сходимость. Следовательно, на него можно сократить и суммы [latex]N + M[/latex]. Максимальный из таких [latex]k[/latex] будет [latex]gcd \left(N, M \right)[/latex].
Полученный результат позволяет сформулировать необходимое условие: если решение есть, то сумма чисел [latex]N[/latex] и [latex]M[/latex] равна некоторой степени двойки с точностью до НОД([latex]N, M[/latex]).
Достаточно условие сходимости.
Пусть [latex]N, M[/latex] — некоторые числа, удовлетворяющие необходимому условию. Тогда [latex]\exists n: N=2^{ n }-M[/latex].
Рассмотрим следующий шаг, предполагая, что [latex]N \ge M[/latex]: [latex]\left(2N \quad 2^{n}-2N\right) \sim \left(N \quad 2^{n-1}-N \right)[/latex]) — задачу удалось свести к подзадаче. Повторяя аналогичную процедуру, на [latex]n[/latex]-м шаге придём в позицию, эквивалентную [latex]\left(1 \quad 2^{0}-1 \right) \sim \left(1 \quad 0 \right)[/latex], т.е. последнему шагу. Следовательно, для любого набора данных, удовлетворяющих необходимому условию, решение существует. Следовательно, условие является необходимым и достаточным, с поправкой на тривиальный случай [latex]N = M[/latex].

Реализация

ideone: http://ideone.com/OxWVLi

#include <cstdio>
inline int gcd(int a, int b){
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
int main()
{
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = (a + b)/gcd(a, b);
    printf("%d\n", (a == b || c == (c & (-c))));
    return 0;
}

#include <cstdio>

inline int gcd(int a, int b){

while(b) b ^= a ^= b ^= a %= b;

return a;

}

int main()

{

int a, b, c;

scanf("%d %d", &a, &b);

c = (a + b)/gcd(a, b);

printf("%d\n", (a == b || c == (c & (-c))));

return 0;

}

ideone: http://ideone.com/Xnupjz

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static int gcd(int a, int b){
        while(b != 0) b ^= a ^= b ^= a %= b;
        return a;
    }
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(); int b = in.nextInt();
        int c = (a + b)/gcd(a, b);
        System.out.println((a == b || c == (c & (-c))) ? 1 : 0);
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static int gcd(int a, int b){

while(b != 0) b ^= a ^= b ^= a %= b;

return a;

}

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int a = in.nextInt(); int b = in.nextInt();

int c = (a + b)/gcd(a, b);

System.out.println((a == b || c == (c & (-c))) ? 1 : 0);

}

Детали реализации

Задачи тура подразумевали лаконичные реализации решений. Использование битовых операций позволяет легко ответить на вопрос, является ли сумма чисел некоторой степенью двойки, а также вычислить НОД двух чисел методом приведения в смятение, для чего используется, на мой взгляд, весьма красивое наблюдение о свойствах функции XOR.