Минимальная реализация алгоритма 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 8527. Неравенство ax ≤ b

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

Задача:

Для заданных целых чисел $a$ и $b$ найти наибольшее и наименьшее целое решение неравенства [latex]ax\leq b [/latex].

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

Два целых числа $a$ и $b$, по модулю не превосходящих $1000$.

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

Если неравенство [latex]a x\leq b [/latex] не имеет решений, то вывести no solution.

Если любое действительное число является решением неравенства [latex]ax\leq b [/latex], то вывести all.

Иначе в одной строке вывести наименьшее и наибольшее целое решение неравенства [latex]ax\leq b [/latex]. Если наименьшего целого решения не существует, вывести -INF. Если наибольшего целого решения не существует, вывести INF.

Тесты:

Входные данные	Выходные данные
0 4	all
0 0	all
0 -1	no solution
289 133	-INF 0
-150 -298	2 INF
3 10	-INF 3
956 0	-INF 0
-3 10	-3 INF
-3 0	0 INF
1000 1000	-INF 1
-1000 -1000	1 INF
-1000 1000	-1 INF

Решение:

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

int main() {
    float a, b; 
    cin >> a >> b;
    if (a == 0 && b >= 0) cout << "all";
    else if (a == 0 && b < 0) cout << "no solution";
    else if ((a > 0 && b >= 0) || (a > 0 && b <= 0)) cout << "-INF " << floor(b / a);
    else cout << ceil(b / a) << " INF"; 
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

float a, b;

cin >> a >> b;

if (a == 0 && b >= 0) cout << "all";

else if (a == 0 && b < 0) cout << "no solution";

else if ((a > 0 && b >= 0) || (a > 0 && b <= 0)) cout << "-INF " << floor(b / a);

else cout << ceil(b / a) << " INF";

return 0;

}

Объяснение:

Задача сводится к решению неравенства $ x\leq\frac{a}{b} $ или $ x\geq\frac{a}{b},$ в зависимости от значений параметров $a$ и $b.$ Поэтому необходимо рассмотреть все возможные варианты значений $a$ и $b$ от которых будет зависеть значение неравенства. Если $a>0$, то выражение будет равносильно $ x\leq\frac{a}{b} $, так как знак неравенства при делении на положительное число не меняется. Поскольку, нам нужно, чтобы $x$ был меньше данного выражения (либо равен), значение которого может быть и дробным (поэтому тип данных $a$ и $b$ дробный, хоть по условию, нам и нужен целый ответ), округляем в меньшую сторону. В обратном случае ($a<0$ и, следовательно, исходное выражение эквивалентно $ x\geq\frac{a}{b}$) нам нужно наоборот, большее значение, поэтому и округление производится в большую сторону. Затем остается рассмотреть только частный случай $a=0$ , что и делается в начале кода.

e-olymp

ideone

Related Images:

e-olymp 7623. Счастливые случаи

26/06/2018 by Даниил Крутоголов

Счастливые случаи

Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

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

В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

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

Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$1$ $1$ $4$	$4$
2	$2$ $4$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$	$12$
3	$3$ $2$ $10$ $10$ $10$ $10$ $4$ $5$	$13$
4	$2$ $2$ $1$ $2$ $3$ $4$	$12$
5	$0$ $0$	$0$

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

#include <iostream>

using namespace std; 

int main() {
    int r, c, a, b, e, d, w = 0;
    cin >> r >> c;
    int **x = new int * [r];
    for (int i = 0; i < r; i++) x[i] = new int[c];
    for (int i = 0; i < r; i++){
        for (int j = 0; j > x[i][j];
        }
    }
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            a = b = e = d = 1;
        for (int q = 0; q < i; q++){
            if (x[i][j] <= x[q][j])
                a = 0;
        }
        for (int q = i+1; q < r; q++){
            if (x[i][j] <= x[q][j])
                b = 0;
        }
        for (int k = 0; k < j; k++){
            if (x[i][j] <= x[i][k])
                e = 0;
        }
        for (int k = j+1; k < c; k++){
            if (x[i][j] <= x[i][k])
                d = 0;
        }
        w+= a + b + e + d;
        }
    }
    cout << w;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, c, a, b, e, d, w = 0;

cin >> r >> c;

int **x = new int * [r];

for (int i = 0; i < r; i++) x[i] = new int[c];

for (int i = 0; i < r; i++){

for (int j = 0; j > x[i][j];

}

for (int i = 0; i < r; i++){

for (int j = 0; j < c; j++){

a = b = e = d = 1;

for (int q = 0; q < i; q++){

if (x[i][j] <= x[q][j])

a = 0;

}

for (int q = i+1; q < r; q++){

if (x[i][j] <= x[q][j])

b = 0;

}

for (int k = 0; k < j; k++){

if (x[i][j] <= x[i][k])

e = 0;

}

for (int k = j+1; k < c; k++){

if (x[i][j] <= x[i][k])

d = 0;

}

w+= a + b + e + d;

}

cout << w;

return 0;

}

Решение задачи

Решение данной задачи состоит в том, чтобы создать цикл, который будет сравнивать все элементы массива. Изначально у нас будут четыре переменных, которые отвечают за каждую из сторон массива, равные единице. Далее мы сравниваем каждый элемент строки с последующими в нужном направлении и если он не является выигрышным, то соответствующей переменной задаем значение ноль. Просуммировав все «выигрышные случаи» мы узнаем количество выигрышных направлений.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 520. Сумма всех

26/12/2017 by Даниил Крутоголов

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]4[/latex]	[latex]6[/latex]
2	[latex]3[/latex]	[latex]3[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]9[/latex]
4	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex]	[latex]10[/latex]
5	[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]	[latex]0[/latex]

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

#include <iostream>
 
using namespace std;
 
int main() {
    long x;
    long sum = 0;
    while (cin >> x){
        sum+= x;
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long x;

long sum = 0;

while (cin >> x){

sum+= x;

}

cout << sum;

return 0;

}

Решение задачи

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 7944. Площадь прямоугольника

23/12/2017 by Даниил Крутоголов

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex] [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]1[/latex] [latex]1[/latex]	[latex]1[/latex]
2	[latex]2[/latex] [latex]4[/latex]	[latex]8[/latex]
3	[latex]511[/latex] [latex]428[/latex]	[latex]218708[/latex]
4	[latex]5555[/latex] [latex]4444[/latex]	[latex]24686420[/latex]
5	[latex]11[/latex] [latex]11[/latex]	[latex]121[/latex]

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

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int a, b;

cin >> a >> b;

cout << a * b << endl;

return 0;

}

Решение задачи

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 165. Симметрия

21/12/2017 by Даниил Крутоголов

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

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

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n, m;
    double k;
    cin >> n;
    m = log2(n);
    k = log2(n);
    while (m != k){
        n = n - (pow(2,m));
        m = log2(n);
        k = log2(n);
    }
    cout << m + 1;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

double k;

cin >> n;

m = log2(n);

k = log2(n);

while (m != k){

n = n - (pow(2,m));

m = log2(n);

k = log2(n);

}

cout << m + 1;

return 0;

}

Решение задачи

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

А394г

12/11/2014 by Іванов Вячеслав Володимирович

Задача
Дана целочисленная квадратная матрица порядка [latex]n[/latex]. Найти номера строк, элементы каждой из которых образуют образуют монотонную последовательность (монотонно убывающую или монотонно возрастающую).

*Строки матрицы нумеруются с единицы, потому их номера в выводе больше соответствующих индексов в массиве на единицу.
Тесты

[latex]n[/latex]

Матрица

Результат

Комментарий

Квадратная матрица первого порядка состоит из одного элемента, следовательно, является и монотонно возрастающей, и монотонно убывающей.

1	1	1
2	2	2
3	3	3

—

Все элементы каждой строки попарно равны.

1	2	2	1
0	1	2	3
0.3	11	-2	3
0	0	1	1

В прочих строках монотонность нарушается

1	2	2
-1	10	15
3	2	1

2, 3

В первой строке последовательность возрастает нестрого.

Алгоритм решения

Анализировать строку на монотонность можно при помощи знака разности соседних элементов. Если при движении по строке слева направо знак изменяется, последовательность не может быть монотонной (дополнительное ограничение для строгой монотонности: разность не должна равняться нулю).
Отдельно следует рассматривать случай [latex]n \le 1[/latex]. По определению, последовательность [latex]\left\{ { a }_{ n } \right\}[/latex] — монотонна [latex]\Leftrightarrow \forall i,j\in N, j>i: a_{ i }\prec a_{ j } (a_{ i }\succ a_{ j })[/latex]. Последовательность из одного элемента имеет вид [latex]\left\{a_{n}\right\} = a_{1}[/latex], следовательно, невозможно выбрать такие [latex]i,j \in N ,j>i[/latex], чтобы выполнилось условие строгой монотонности. Рассмотренный пример является частным случаем понятия «vacuous truth», часто применяемого при доказательстве теорем.

Программный код

#include <cstdio>
int sign(double x){
	return (x > 0) - (x < 0);
}

int main() {
	size_t n; scanf("%d", &n);
	double x[n][n];
	for(size_t i = 0; i < n; i++)
		for(size_t j = 0; j < n; j++)
			scanf("%lf", &x[i][j]);
			
	if(n >= 1) {
		for(size_t i = 0; i < n; i++){
			/*последовательность монотонна, если сохраняет знак разность
			между N-м и (N-1)-м членом последовательности.*/
			int prev_sign = sign(x[i][1] - x[i][0]); //знак разности первой пары чисел
			bool monotonic = true;
			for(size_t j = 1; j < n; j++){
				int new_sign = sign(x[i][j] - x[i][j - 1]); //знак разности следующей пары
				if(prev_sign * new_sign <= 0){
					monotonic = false; 
					j = n;
				}
				prev_sign = new_sign; //новая пара для сравнения
			}
			if(monotonic) printf("%d ", i + 1);
		}
	}
	else printf("1\n");
	return 0;
}

#include <cstdio>

int sign(double x){

return (x > 0) - (x < 0);

}

int main() {

size_t n; scanf("%d", &n);

double x[n][n];

for(size_t i = 0; i < n; i++)

for(size_t j = 0; j < n; j++)

scanf("%lf", &x[i][j]);

if(n >= 1) {

for(size_t i = 0; i < n; i++){

/*последовательность монотонна, если сохраняет знак разность

между N-м и (N-1)-м членом последовательности.*/

int prev_sign = sign(x[i][1] - x[i][0]); //знак разности первой пары чисел

bool monotonic = true;

for(size_t j = 1; j < n; j++){

int new_sign = sign(x[i][j] - x[i][j - 1]); //знак разности следующей пары

if(prev_sign * new_sign <= 0){

monotonic = false;

j = n;

}

prev_sign = new_sign; //новая пара для сравнения

}

if(monotonic) printf("%d ", i + 1);

}

else printf("1\n");

return 0;

}

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static void main(String args[]) {
 		Scanner in = new Scanner(System.in);
 		int n = in.nextInt();
 		double[][] x = new double[n][n];
 		for(int i = 0; i < n; i++)   		
 			for(int j = 0; j < n; j++)
 				x[i][j] = in.nextDouble();
 		if(n >= 1){
 			for(int i = 0; i < n; i++){
 				/*последовательность монотонна, если сохраняет знак разность
            	между N-м и (N-1)-м членом последовательности.*/
            	double prevSign = Math.signum(x[i][1] - x[i][0]); //знак разности первой пары чисел
            	boolean monotonic = true;
            	for(int j = 1; j < n; j++){
	                double newSign = Math.signum(x[i][j] - x[i][j-1]); //знак разности следующей пары
                	if(prevSign * newSign <= 0){
	                    monotonic = false; 
                    	j = n;
                	}
                	prevSign = newSign; //новая пара для сравнения
            	}
            	if(monotonic) System.out.println(i+1);
	        }
    	}
    	else System.out.println(1);
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double[][] x = new double[n][n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

x[i][j] = in.nextDouble();

if(n >= 1){

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

/*последовательность монотонна, если сохраняет знак разность

между N-м и (N-1)-м членом последовательности.*/

double prevSign = Math.signum(x[i][1] - x[i][0]); //знак разности первой пары чисел

boolean monotonic = true;

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

double newSign = Math.signum(x[i][j] - x[i][j-1]); //знак разности следующей пары

if(prevSign * newSign <= 0){

monotonic = false;

j = n;

}

prevSign = newSign; //новая пара для сравнения

}

if(monotonic) System.out.println(i+1);

}

else System.out.println(1);

}

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

Считывание элементов строки может прекратиться в трех случаях: если монотонность сменяется с возрастания на убывание (или наоборот), или если найдены два равных соседних элемента. Для выхода из внутреннего цикла применяется присваивание [latex]j = n[/latex].
Для корректной работы внутреннего цикла первый элемент строки считывается перед ним.
Проверить, изменяется ли знак разности соседних элементов последовательности можно двумя способами: первый подразумевает умножение двух разностей, второй — реализацию функции signum(). Так как при умножении можно выйти за границы типа, выбран был второй способ.

Программа доступна для тестирования по ссылке: http://ideone.com/n60As6.
Реализация на Java: http://ideone.com/CnFow1