Эффективный подсчет больших чисел

@_lUserl_ · Регистрация: 20.07.2018

Студворк — интернет-сервис помощи студентам

Здравствуйте. Пытаюсь реализовать криптографический алгоритм SAFER+, и встала задача генерации слов смещения. Они получаются путем такой операции:

B(i,j) = 45 ^ (45 ^ (17i + j) mod 257) mod 257, где B(i, j) - j-тый байт в i-том слове смещения; i = 2, ..., 17; j = 1, ..., 16,
то есть в итоге должно получиться 16 сло смещения по 16 байт каждое.

Слова планирую хранить в матрице 16х16:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const unsigned char B[16][16] = {
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
};

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

Verevkin · 29.10.2023, 15:18

Сообщение от _lUserl_

Думаю не стоит даже пытаться в тупую вычислить все это дело.

Можно написать одноразовую прогу, которая это и сделает. В чём проблема-то? У тебя все пальцы сломаны?

@_lUserl_ · 29.10.2023, 15:22 **[ТС]**

Ну вот проблема в том, что я не особо понимаю как написать эту "одноразовую прогу", так как плохо помню c++/c

@Pphantom · 29.10.2023, 15:23

А оно обязательно нужно на C++? Намного проще сгенерировать это где угодно, где поддерживается длинная арифметика, а потом использовать готовый результат.

Вот, например, код для Maxima:

Code
1
2
 B(i,j):=mod(45^(mod(45^(17*i+j),257)),257);
for i:2 thru 17 do for j:1 thru 16 do print(B(i,j));

На написание ушла минута, выполняется это за тысячные доли секунды.

Verevkin · 29.10.2023, 15:24

Сообщение от _lUserl_

Ну вот проблема в том, что я не особо понимаю как написать эту "одноразовую прогу", так как плохо помню c++/c

Как же ты собираешься писать всё остальное?

Сообщение от _lUserl_

реализовать криптографический алгоритм SAFER+

А?

@Pphantom · 29.10.2023, 15:33

Ну, собственно, если нужен результат, то вот:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
70,151,177,186,163,183,16,10,197,55,179,201,90,40,172,100
236,171,170,198,103,149,88,13,248,154,246,110,102,220,5,61
138,195,216,137,106,233,54,73,67,191,235,212,150,155,104,160
93,87,146,31,213,113,92,187,34,193,190,123,188,153,99,148
42,97,184,52,50,25,253,251,23,64,230,81,29,65,68,143
221,4,128,222,231,49,214,127,1,162,247,57,218,111,35,202
58,208,28,209,48,62,18,161,205,15,224,168,175,130,89,44
125,173,178,239,194,135,206,117,6,19,2,144,79,46,114,51
192,141,207,169,129,226,196,39,47,108,122,159,82,225,21,56
252,32,66,199,8,228,9,85,94,140,20,118,96,255,223,215
250,11,33,256,26,249,166,185,232,158,98,76,217,145,80,210
24,180,7,132,234,91,164,200,14,203,72,105,75,78,156,53
69,77,84,229,37,60,12,74,139,63,204,167,219,107,174,244
45,243,124,109,157,181,38,116,242,147,83,176,240,17,237,131
182,3,22,115,59,30,142,112,189,134,27,71,126,36,86,241
136,70,151,177,186,163,183,16,10,197,55,179,201,90,40,172

Verevkin · 29.10.2023, 15:40

Сообщение от Pphantom

Ну, собственно, если нужен результат, то вот:

У меня, почему-то, получился другой результат.
Где я накосячил?

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const unsigned char B[16][16] = 
{
  { 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, 0x30, 0x31, 0x32 }, 
  { 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, 0x40, 0x41, 0x42, 0x43 }, 
  { 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54 }, 
  { 0x56, 0x57, 0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, 0x60, 0x61, 0x62, 0x63, 0x64, 0x65 }, 
  { 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76 }, 
  { 0x78, 0x79, 0x7A, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87 }, 
  { 0x89, 0x8A, 0x8B, 0x8C, 0x8D, 0x8E, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98 }, 
  { 0x9A, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9 }, 
  { 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB2, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA }, 
  { 0xBC, 0xBD, 0xBE, 0xBF, 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB }, 
  { 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC }, 
  { 0xDE, 0xDF, 0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xED }, 
  { 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE }, 
  { 0x00, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E }, 
  { 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F }, 
  { 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, 0x30 }
};

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
 
/* (i,j) = 45 ^ (45 ^ (17i + j) mod 257) mod 257, где B(i, j) - j-тый байт 
 в i-том слове смещения; i = 2, ..., 17; j = 1, ..., 16,
то есть в итоге должно получиться 16 сло смещения по 16 байт каждое.*/
void print_saver_table(void)
{
  printf("const unsigned char B[16][16] = \n{\n");
  for (auto i = 2; i != 18; i++)
  {
    printf("  {");
    for (auto j = 1; j != 17; j++)  
    {
      uint8_t x = (45 ^ (45 ^ (17 * i + j) % 257)) % 257;
      printf("%s0x%.2X",j != 1 ? ", " : " ", x);
    }  
    
    printf(" }%s\n", i != 17 ? ",": "");
  }  
  printf("};\n");
}
 
int main()
{ 
  print_saver_table();
  return 0;
}

@Pphantom · 29.10.2023, 15:45

Кхм, возможно, это я накосячил... _lUserl_, что вы обозначали ^ ?

Verevkin · 29.10.2023, 15:46

Сообщение от Pphantom

Кхм, возможно, это я накосячил... _lUserl_, что вы обозначали ^ ?

XOR

@_lUserl_ · 29.10.2023, 15:46 **[ТС]**

Сообщение от Pphantom

что вы обозначали ^

Возведение в степень

@Pphantom · 29.10.2023, 15:48

Сообщение от Verevkin

XOR

Ну вот в этом и дело.

Сообщение от _lUserl_

Возведение в степень

Ага, тогда я интерпретировал это правильно, а Verevkin - нет.

P.S. Отсюда мораль: математические формулы надо оформлять как формулы, а операторы языков программирования - как код на ЯП. А то ведь могли и оба не угадать, что на самом деле имелось в виду.

Verevkin · 29.10.2023, 15:49

Сообщение от _lUserl_

Возведение в степень

А чего не написал формулу?

@_lUserl_ · 29.10.2023, 15:52 **[ТС]**

Сообщение от Pphantom

Отсюда мораль: математические формулы надо оформлять как формулы, а операторы языков программирования - как код на ЯП

Действительно, в следующий раз не буду вызывать такое недопонимание. Всем спасибо за ответы, очень помогли

Verevkin · 29.10.2023, 16:02

Сообщение от Pphantom

Ага, тогда я интерпретировал это правильно, а Verevkin - нет.

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

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const unsigned char B[16][16] = 
{
  { 0x46, 0x97, 0xB1, 0xBA, 0xA3, 0xB7, 0x10, 0x0A, 0xC5, 0x37, 0xB3, 0xC9, 0x5A, 0x28, 0xAC, 0x64 },
  { 0xEC, 0xAB, 0xAA, 0xC6, 0x67, 0x95, 0x58, 0x0D, 0xF8, 0x9A, 0xF6, 0x6E, 0x66, 0xDC, 0x05, 0x3D },
  { 0x8A, 0xC3, 0xD8, 0x89, 0x6A, 0xE9, 0x36, 0x49, 0x43, 0xBF, 0xEB, 0xD4, 0x96, 0x9B, 0x68, 0xA0 },
  { 0x5D, 0x57, 0x92, 0x1F, 0xD5, 0x71, 0x5C, 0xBB, 0x22, 0xC1, 0xBE, 0x7B, 0xBC, 0x99, 0x63, 0x94 },
  { 0x2A, 0x61, 0xB8, 0x34, 0x32, 0x19, 0xFD, 0xFB, 0x17, 0x40, 0xE6, 0x51, 0x1D, 0x41, 0x44, 0x8F },
  { 0xDD, 0x04, 0x80, 0xDE, 0xE7, 0x31, 0xD6, 0x7F, 0x01, 0xA2, 0xF7, 0x39, 0xDA, 0x6F, 0x23, 0xCA },
  { 0x3A, 0xD0, 0x1C, 0xD1, 0x30, 0x3E, 0x12, 0xA1, 0xCD, 0x0F, 0xE0, 0xA8, 0xAF, 0x82, 0x59, 0x2C },
  { 0x7D, 0xAD, 0xB2, 0xEF, 0xC2, 0x87, 0xCE, 0x75, 0x06, 0x13, 0x02, 0x90, 0x4F, 0x2E, 0x72, 0x33 },
  { 0xC0, 0x8D, 0xCF, 0xA9, 0x81, 0xE2, 0xC4, 0x27, 0x2F, 0x6C, 0x7A, 0x9F, 0x52, 0xE1, 0x15, 0x38 },
  { 0xFC, 0x20, 0x42, 0xC7, 0x08, 0xE4, 0x09, 0x55, 0x5E, 0x8C, 0x14, 0x76, 0x60, 0xFF, 0xDF, 0xD7 },
  { 0xFA, 0x0B, 0x21, 0x00, 0x1A, 0xF9, 0xA6, 0xB9, 0xE8, 0x9E, 0x62, 0x4C, 0xD9, 0x91, 0x50, 0xD2 },
  { 0x18, 0xB4, 0x07, 0x84, 0xEA, 0x5B, 0xA4, 0xC8, 0x0E, 0xCB, 0x48, 0x69, 0x4B, 0x4E, 0x9C, 0x35 },
  { 0x45, 0x4D, 0x54, 0xE5, 0x25, 0x3C, 0x0C, 0x4A, 0x8B, 0x3F, 0xCC, 0xA7, 0xDB, 0x6B, 0xAE, 0xF4 },
  { 0x2D, 0xF3, 0x7C, 0x6D, 0x9D, 0xB5, 0x26, 0x74, 0xF2, 0x93, 0x53, 0xB0, 0xF0, 0x11, 0xED, 0x83 },
  { 0xB6, 0x03, 0x16, 0x73, 0x3B, 0x1E, 0x8E, 0x70, 0xBD, 0x86, 0x1B, 0x47, 0x7E, 0x24, 0x56, 0xF1 },
  { 0x88, 0x46, 0x97, 0xB1, 0xBA, 0xA3, 0xB7, 0x10, 0x0A, 0xC5, 0x37, 0xB3, 0xC9, 0x5A, 0x28, 0xAC }
};

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
 
// возведение в степень по модулю
unsigned pow_mod(unsigned base, unsigned exponent, unsigned modulo)
{
  if (!exponent) return 1 % modulo;
  if (!base) return 0;
  if (base == 1) return base % modulo;
  
  unsigned p = 1;
  while (exponent--)
    p *= base, p %= modulo;
  return p;
}
 
/* (i,j) = 45 ^ (45 ^ (17i + j) mod 257) mod 257, где B(i, j) - j-тый байт 
 в i-том слове смещения; i = 2, ..., 17; j = 1, ..., 16,
то есть в итоге должно получиться 16 сло смещения по 16 байт каждое.*/
void print_saver_table(void)
{
  printf("const unsigned char B[16][16] = \n{\n");
  for (auto i = 2; i != 18; i++)
  {
    printf("  {");
    for (auto j = 1; j != 17; j++)  
    {
      uint8_t x = pow_mod(45, pow_mod(45, 17 * i + j, 257), 257); //(45 ^ (45 ^ (17 * i + j) % 257)) % 257;
      printf("%s0x%.2X",j != 1 ? ", " : " ", x);
    }  
    
    printf(" }%s\n", i != 17 ? ",": "");
  }  
  printf("};\n");
}
 
int main()
{ 
  print_saver_table();
  return 0;
}

@Pphantom · 29.10.2023, 16:10

Verevkin, ну да, все правильно, только #include <cstdint> стоило бы добавить.

Verevkin · 29.10.2023, 16:11

Сообщение от Pphantom

только #include <cstdint> стоило бы добавить.

Зачем?

@Pphantom · 29.10.2023, 16:19

Сообщение от Verevkin

Зачем?

Чтобы никакие компиляторы не ругались, ибо по стандарту положено.

Verevkin · 29.10.2023, 16:22

Сообщение от Pphantom

Чтобы никакие компиляторы не ругались, ибо по стандарту положено.

наложено!

Кому надо, тот сам и добавит.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

Эффективный подсчет больших чисел

Решение

Решение

@_lUserl_ 4 / 4 / 0 Регистрация: 20.07.2018 Сообщений: 279
	29.10.2023, 15:22 [ТС]
	Ну вот проблема в том, что я не особо понимаю как написать эту "одноразовую прогу", так как плохо помню c++/c 0

@Pphantom 2268 / 1524 / 712 Регистрация: 17.03.2022 Сообщений: 4,901
	29.10.2023, 15:45
	Кхм, возможно, это я накосячил... _lUserl_, что вы обозначали ^ ? 0

@Pphantom 2268 / 1524 / 712 Регистрация: 17.03.2022 Сообщений: 4,901
	29.10.2023, 16:10
	Verevkin, ну да, все правильно, только `#include <cstdint>` стоило бы добавить. 0