Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5   вперед  Ctrl      все
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
Dima T
Погуглил немного: оказывается RSA c 32-битным ключом это пара десятков строк кода ))) Пошел писать.

Строк мало, а в 32 бита вписаться проблематично :( Есть проблемы с генерацией ключей.
какие проблемы то? гдет тема была с генерацией простых чисел

фигня только выйдет, взламывается на ура тупым перебором
29 дек 18, 00:15    [21776126]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Победил разрядность, черновик без тюнинга производительности
	// Создание ключей
	rand_init(); // Инициализация ГСЧ
	uint32_t p, q, n, y, e, d;
	while (true) { // для возврата при переполнении
		cout << "Please wait... Key generation procces." << endl;
		// 1. Выбираются два различных случайных простых числа p и q заданного размера.
		do {
			p = rand32_prime(1024, 65535); // случайное простое в диапазоне от ... до ...
			q = rand32_prime(1024, 65535);
			// 2. Вычисляется их произведение n = p * q, которое называется модулем.
			n = p * q;
		} while(n < 0xFFFFF || n > 0xFFFFFF); // для шифрования двухбайтовых значений 
		// 3. Вычисляется значение функции Эйлера от числа n: y = (p - 1) * (q - 1)
		y = (p - 1)*(q - 1);
		// 4. Выбирается целое число e ( 1 < e < y) взаимно простое со значением y
		do {
			//e = rand32(5, y - 1); // rand32() случайное в диапазоне от ... до ...
			e = rand32(32, 255); // при больших e не хватает разрядности при подборе d
		} while (gcd(e, y) != 1);
		// 5. Вычисляется число d, удовлетворяющее сравнению (e*d) % y = 1
		uint32_t d_max = 4294967295 / e - 1; // наибольшее d 32 бита
		d = rand32(y / e, d_max);
		while (d < d_max && e*d % y != 1) {
			d++;
		}
		if (d < d_max) break;
	}
	// Готово: {e,n} - открытый ключ, {d,n} - закрытый ключ

Далее шифрование
uint32_t crypt = pow_mod(data, e, n);

и расшифровка
uint32_t decrypt = pow_mod(crypt, d, n);

где
pow_mod(base, exp, n) { 
   return (base ^ exp) % n; // Формула из учебников, чтобы понятно было
}

Тут еще один вопрос: я не совсем понимаю про допустимую разрядность шифруемого. Т.к. в итоге происходит "% n", то могу ли я ожидать что все значения до n (0 <= x < n) будут корректно зашифрованы и расшифрованы?
Планирую двухбайтными блоками шифровать, плюс флаг для указания что один байт зашифрован, т.е. шифруемые значения 0 <= x <= 0x100FF. Поэтому ограничил 0x100000 <= n <= 0xFFFFFF. Т.е. минимальный n почти в 16 раз больше максимального шифруемого.
Тесты погоняю, но ключей множество, все комбинации не проверить. Хотелось бы найти какое-то мат.доказательство.
29 дек 18, 09:25    [21776202]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
Тут еще один вопрос: я не совсем понимаю про допустимую разрядность шифруемого. Т.к. в итоге происходит "% n", то могу ли я ожидать что все значения до n (0 <= x < n) будут корректно зашифрованы и расшифрованы?
не все, ограничение из теоремы Эйлера
m, p1, p2 - должны быть взаимнопросты
29 дек 18, 09:33    [21776209]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
kealon(Ruslan)
Dima T
Тут еще один вопрос: я не совсем понимаю про допустимую разрядность шифруемого. Т.к. в итоге происходит "% n", то могу ли я ожидать что все значения до n (0 <= x < n) будут корректно зашифрованы и расшифрованы?
не все, ограничение из теоремы Эйлера
m, p1, p2 - должны быть взаимнопросты

В смысле для pow_mod(base, exp, n) взаимнопросты exp и n, т.к. специально генерятся, а base тоже должно быть взимнопростое к exp и n?
29 дек 18, 09:38    [21776213]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
// 5. Вычисляется число d, удовлетворяющее сравнению (e*d) % y = 1
		uint32_t d_max = 4294967295 / e - 1; // наибольшее d 32 бита
		d = rand32(y / e, d_max);
		while (d < d_max && e*d % y != 1) {
			d++;
		}
		if (d < d_max) break;

вот это нехорошо, гугли расширенный алгоритм Евклида
29 дек 18, 09:40    [21776215]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
kealon(Ruslan)
пропущено...
не все, ограничение из теоремы Эйлера
m, p1, p2 - должны быть взаимнопросты

В смысле для pow_mod(base, exp, n) взаимнопросты exp и n, т.к. специально генерятся, а base тоже должно быть взимнопростое к exp и n?
не к експоненте, а к p и q
29 дек 18, 09:46    [21776216]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
kealon(Ruslan)
Dima T
пропущено...

В смысле для pow_mod(base, exp, n) взаимнопросты exp и n, т.к. специально генерятся, а base тоже должно быть взимнопростое к exp и n?
не к експоненте, а к p и q

Добавил тупой перебор
	for (uint32_t i = 0; i != 65792; i++) {
		uint32_t crypt = pow_mod(i, e, n);
		uint32_t decrypt = pow_mod(crypt, d, n);
		if (i != decrypt) {
			cout << "!!! ERROR: crypt " << i << " decrypt " << decrypt << endl;
			break;
		}
	}

Не срабатывает, хотя вот например значения
{6449,1823} - {p, q}
{253,11756527} - {e,n}
{15138069,11756527} - {d,n}

Как понимаю должно сглючить на каждом кратном 1823, т.е. 3646, 5469, 7292, 9115 и т.д. но работает.

Оставим этот вопрос открытым, пока просто добавлю эту проверку в генерацию ключей.

kealon(Ruslan)
вот это нехорошо, гугли расширенный алгоритм Евклида

Евклида загуглил, спасибо за подсказку, а то хотел свой велосипед изобретать.

kealon(Ruslan)
фигня только выйдет, взламывается на ура тупым перебором

Думаю прежде чем тюнинг устраивать надо перебор запустить: генерить ключи и писать в какой-нибудь std::map, посмотреть как быстро будет увеличиваться количество уникальных комбинаций, как часто повторы случаются.
Если их относительно немного получится, например миллиард, то можно сложить их в табличку и по открытому ключу получать закрытый.

Написал, посмотрел код:
0x100000 <= n <= 0xFFFFFF
32 <= e <= 255
т.е. n максимум 2^24, e - 2^8 итого максимум 2^32 комбинаций или 4 лярда, которые уже в табличку влазят. Причем не все комбинации допустимы, т.е. допустимых комбинаций будет намного меньше. Печалька (((

Для начала разрядность n и e надо повысить.
29 дек 18, 10:32    [21776241]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
Думаю прежде чем тюнинг устраивать надо перебор запустить: генерить ключи и писать в какой-нибудь std::map, посмотреть как быстро будет увеличиваться количество уникальных комбинаций, как часто повторы случаются.
Если их относительно немного получится, например миллиард, то можно сложить их в табличку и по открытому ключу получать закрытый.

Написал, посмотрел код:
0x100000 <= n <= 0xFFFFFF
32 <= e <= 255
т.е. n максимум 2^24, e - 2^8 итого максимум 2^32 комбинаций или 4 лярда, которые уже в табличку влазят. Причем не все комбинации допустимы, т.е. допустимых комбинаций будет намного меньше. Печалька (((

Для начала разрядность n и e надо повысить.
Зачем???
просто n разложить на множители и дальше расчёт ключей тривиален - вот и весь "взлом"
29 дек 18, 11:46    [21776286]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
kealon(Ruslan)
просто n разложить на множители и дальше расчёт ключей тривиален - вот и весь "взлом"

Точно. На перебор всех простых от 2 до sqrt(n) надо меньше секунды. Потом немного перебора с подбором d.

Все равно допилю, без исходников сложно понять что это за алгоритм. А в случае необходимости всегда можно перейти на полноценный RSA.
29 дек 18, 14:04    [21776411]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
kealon(Ruslan)
Dima T
// 5. Вычисляется число d, удовлетворяющее сравнению (e*d) % y = 1
		uint32_t d_max = 4294967295 / e - 1; // наибольшее d 32 бита
		d = rand32(y / e, d_max);
		while (d < d_max && e*d % y != 1) {
			d++;
		}
		if (d < d_max) break;

вот это нехорошо, гугли расширенный алгоритм Евклида

Алгоритм нагуглил, только как его тут применить не понимаю.
Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d.
29 дек 18, 14:11    [21776415]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Вроде нашел как
https://foxford.ru/wiki/informatika/rasshirennyy-algoritm-evklida
Одним из применений расширенного алгоритма Евклида является нахождение обратного элемента в кольце вычетов по модулю....
29 дек 18, 14:18    [21776424]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47076
Dima T
Элементарно: если кто-то назовется Алисой, то при этом реальная Алиса зайти не сможет, поэтому она позвонит и скажет: "ваша корявая прога не работает".

Вопрос не во входе, вопрос в регистрации нового пользователя. В системе ещё нет Алисы. Как Алиса докажет, что это она Алиса, а не Хрен-с-горы, который ею представился час назад?
29 дек 18, 14:39    [21776443]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
Вроде нашел как
https://foxford.ru/wiki/informatika/rasshirennyy-algoritm-evklida
Одним из применений расширенного алгоритма Евклида является нахождение обратного элемента в кольце вычетов по модулю....

не помню откуда брал, нерекурсивный вариант:
// ax + by = gcd(a,b)
procedure gcdMain(a, b: TInt; out x, y, d: TInt);
var
  q, r, x1, x2, y1, y2: TInt;
begin
  if (b = 0) then
  begin
    d := a;
    x := 1;
    y := 0;
    Exit;
  end;

  x2 := 1;
  x1 := 0;
  y2 := 0;
  y1 := 1;
  while (b > 0)do
  begin
    q := a div b;
    r := a - q * b;
    x := x2 - q * x1;
    y := y2 - q * y1;

    a := b;
    b := r;
    x2 := x1;
    x1 := x;
    y2 := y1;
    y1 := y;
  end;
  d := a;
  x := x2;
  y := y2;
end;
29 дек 18, 15:22    [21776475]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Dimitry Sibiryakov
Dima T
Элементарно: если кто-то назовется Алисой, то при этом реальная Алиса зайти не сможет, поэтому она позвонит и скажет: "ваша корявая прога не работает".

Вопрос не во входе, вопрос в регистрации нового пользователя. В системе ещё нет Алисы. Как Алиса докажет, что это она Алиса, а не Хрен-с-горы, который ею представился час назад?

Это-то тут при чем? Тут каждый сам решает как при регистрации убедиться что пользователь тот за кого себя выдает.
Эта проблема не этого топика, но она мне известна, как-то ее тоже надо будет решать, как один из вариантов вводить спец.учетку(и) админа: юзер саморегается, но изначально получает права писать только админам, передает админам инфу о себе, на основании полученной инфы админ дает серверу команду подтверждения или удаления новичка. В общем это тема для отдельного топика.

Суть моей проблемы в том чтобы никто не смог писать от лица уже имеющейся учетки.
Например тебе в вацап напишут с неизвестного номера - ничего страшного, главное чтобы левые люди не писали с известных тебе номеров. Т.е. получатель изначально знает от кого принимать сообщения. Я эту проблему решаю.

Например резервное копирование: есть получатель "backup", ему сообщил что слать файлы могут "proga1", "proga2" и "proga3". От этих учеток принимает, остальным пишет "Извините, а вы кто?"
29 дек 18, 15:33    [21776483]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
kealon(Ruslan)
не помню откуда брал, нерекурсивный вариант:

Спасибо. А то в инете только с рекурсией.
29 дек 18, 15:36    [21776485]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Dima T
kealon(Ruslan)
не помню откуда брал, нерекурсивный вариант:

Спасибо. А то в инете только с рекурсией.
та нет, мусорка просто та ещё

тынц
29 дек 18, 15:37    [21776487]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
kealon(Ruslan)
Dima T
пропущено...

Спасибо. А то в инете только с рекурсией.
та нет, мусорка просто та ещё

тынц

+ Я уже твой переписал
// Расширенный алгоритм Евклида. ax + by = gcd(a,b)
uint32_t gcdext(uint32_t a, uint32_t b, int32_t & x, int32_t & y) {
	if (b == 0) {
		x = 1; y = 0;
		return b;
	}

	uint32_t q, r;
	int32_t x1, x2, y1, y2;

	x2 = 1;
	x1 = 0;
	y2 = 0;
	y1 = 1;
	while (b > 0) {
		q = a / b;
		r = a - q * b;
		x = x2 - q * x1;
		y = y2 - q * y1;

		a = b;
		b = r;
		x2 = x1;
		x1 = x;
		y2 = y1;
		y1 = y;
	}
	x = x2;
	y = y2;
	return a;
}

Вроде работает
29 дек 18, 16:05    [21776509]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Затестил перебор. За полчаса нагенерил 7 млн. пар ключей, количество уникальных остановилось на 3`607`581 и даже по одному не добавляется. Можно ломать таблицей ключей )))

Понаблюдаю еще пару часов.
29 дек 18, 17:53    [21776558]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
kealon(Ruslan)
Dima T
пропущено...

Строк мало, а в 32 бита вписаться проблематично :( Есть проблемы с генерацией ключей.
какие проблемы то? гдет тема была с генерацией простых чисел

фигня только выйдет, взламывается на ура тупым перебором

Тест Миллера-рабина применяется. Для чисел которые во много раз больше чем мы генерили несколько лет назад.
29 дек 18, 18:04    [21776563]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
mayton
Тест Миллера-рабина применяется. Для чисел которые во много раз больше чем мы генерили несколько лет назад.
этот тест для проверки простоты числа используется, когда ищут пару для ключа.
29 дек 18, 18:34    [21776570]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Dima T
Затестил перебор. За полчаса нагенерил 7 млн. пар ключей, количество уникальных остановилось на 3`607`581 и даже по одному не добавляется. Можно ломать таблицей ключей )))

Понаблюдаю еще пару часов.

Полтора часа прошло, 27 млн. обработано, а уникальных те же 3`607`581. Все понятно, вырубаю.
29 дек 18, 19:28    [21776586]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Оказывается Тест Миллера — Рабина иногда имеет ложноположительные срабатывания
Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.

Наткнулся на is_prime(233 * 1103) дает true, я на его основе делаю пару ключей, естественно они не рабочие.

Как с этим бороться?
30 дек 18, 10:35    [21776823]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Да. Это нормально.
30 дек 18, 11:26    [21776831]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
А все-таки, ключ - это одно число, или система чисел?
30 дек 18, 13:48    [21776870]     Ответить | Цитировать Сообщить модератору
 Re: Авторизация без сервера  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
С точки зрения криптографии ключ - это просто массив битов.

Но для нашего (человеческого восприятия) мы можем его представлять в виде
- Целого десятичного числа: 12345678
- Двоично десятичного (binhex) Например: 00 FF AB C1
- Base64 - кодированного представления (система счисления с основанием 64)

Но есть формы генерации ключа когда он должен удовлетворять каким-то требованиям
Разложимость на небольшое число простых множителей - это просто один из частных случаев.

Для симметричной криптографии (например шифр DES) например ключ это просто массив из 56 битов.
Для тройного ДЕС-а - соотвествтенно бутерброд из трех ключей 3*56. И формулы там - другие.
Но в большинстве случаев это просто очень хороший случайный поток битов. Без повторов и авто-корреляций.

Есть формулы отображающие пароль в ключ. Но они все соотв. имею слабые места зависящие от
длины пароля.

Выше Дима привёл замечание к методу Раввина-Миллера. Од даёт ложные сообщения о том что число простое.
Но это допустимо. Во первых у него - ошеломительная скорость по сравнению с традиционными методами.
Во вторых он параметризируется числом раундов. (Здесь я точно не помню надо почиать). Ну вобщем
в беря во внимание длинну целых чисел с коротыми он работает - его предсказание простоты вполне
себе подходит для практических задач.
30 дек 18, 14:02    [21776880]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить