перемножение байт из массива и сложение. Что это за алгоритм?

Тема в разделе "WASM.CRYPTO", создана пользователем Aids, 24 июн 2011.

  1. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    Aids
    Ссылки на методы рассчета обратной матрицы есть в вики...
    Главное отличие - все операции выполняются по определенному модулю(основанию).
    Самое главное - операция деления (и связанное с ним обратное число):
    Код (Text):
    1.  a' = 1/a
    записывается как
    Код (Text):
    1. a'*a = 1 mod m
    Например:
    Код (Text):
    1. 3*171 = 1 mod 256
    Поэтому, приведенный вами алгоритм в #15 может быть использован (я не сужу о его правильности для вещественных чисел) с модификацией вычислений:
    1) вместо флоат - байт
    2) вместо деления - умножение на обратное число(см. выше)...

    с учетом того, что было озвучено в #12
    Лично я предпочел бы поиск обратной матрицы (n*n) методом решения n СЛАУ (тоже в вики описан)...
     
  2. Aids

    Aids New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2007
    Сообщения:
    275
    Всё я похоже понял как считать.
    1) Рассчитываю стандартным образом обратную матрицу.(она уже посчитана)
    2) Домножаю её на число K что бы привести все элементы к целому виду, получаю матрицу M
    3) k- это определитель, по расширенному алгоритму эвклида нахожу обратное от k по основанию 256, пусть число -a
    4) (a*M)%256 - это и есть обратная матрица по основанию 256
    расширенный алгоритм эвклида можно взять тут
    http://volvo71.narod.ru/faq_folder/code_text.htm

    Вечером попробую всё это проделать
     
  3. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Aids
    Нельзя так делать. Какое домножение на K. Арифметика по модулю 256 не может быть просто реализована через флоат. Возьми таблицу обратных из аттача и в формуле замени /а на *обратное(а)
     
  4. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    В поле по модулю 256 не каждый элемент обратим!
     
  5. Lukovchanin

    Lukovchanin New Member

    Публикаций:
    0
    Регистрация:
    25 июн 2011
    Сообщения:
    3
    Поэтому СЛАУ ...
     
  6. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    В кольцах нет метода Гаусса!
     
  7. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    Вот это матрица, обратная по модулю 256 к "noname_2_table2", если конечно в том файле была стандартная построчная запись :

    Код (Text):
    1. 50,59,7D,06,7E,0F,DD,A2,B5,88,5C,A6,66,7E,9D,BB,E5,08,2C,C9,CA,6C,06,6A,98,34,5C,9E,9C,84,94,C0,18,AA,91,B8,A1,F7,34,73,C6,CD,22,90,F2,FA,C8,5C,94,44,9D,01,
    2. 7C,45,A7,FA,88,7A,41,CA,81,96,1B,EE,40,1C,82,10,15,2C,E2,7D,69,9D,89,D9,A1,4D,AD,12,46,B5,B1,92,63,C1,A4,B9,2F,DE,0B,8A,EC,54,E0,A4,0F,D6,DA,74,A1,57,EF,AA,
    3. E5,20,18,E9,3B,20,54,C3,44,83,EF,E4,47,86,04,8D,D4,89,41,45,A7,65,EA,CB,CE,01,20,4E,0F,20,64,E0,84,7D,57,29,88,1A,C3,58,D7,D5,DF,5F,F0,3C,CF,60,BE,A2,6B,62,
    4. 78,73,41,49,C6,C4,DD,05,25,2E,48,09,8C,DD,CE,FF,50,E4,04,BA,45,D3,0A,6C,26,8C,0E,19,36,52,11,4B,28,23,EE,08,3C,48,98,01,AC,2A,A3,0C,46,67,06,D4,5A,25,1F,CF,
    5. D6,A7,F7,71,B0,1E,C8,A0,84,C1,BC,67,7F,1F,F8,EE,7B,B4,D9,AA,6B,BB,7D,D1,FA,44,86,11,6F,86,1A,81,D4,76,2E,D8,57,99,05,DD,F0,16,F3,1E,44,0F,67,E5,CA,31,29,68,
    6. 2C,8A,DF,40,F0,9B,D6,1C,57,AF,FF,B7,85,6B,38,07,E3,A5,CD,B8,C2,7A,3F,D8,41,9A,44,D4,70,E7,0E,A3,B5,3F,D0,41,6F,95,7F,5F,DA,47,D6,59,33,AB,9C,68,1C,EB,29,19,
    7. 41,14,27,FD,3C,69,96,A2,B6,FD,12,C3,CF,81,59,BC,C0,5A,08,40,BF,F7,A5,4E,24,61,E2,61,C9,13,20,E8,B6,0D,33,F5,FE,24,65,39,E4,9C,BD,30,42,F8,81,99,2C,11,F9,29,
    8. D0,66,76,80,A0,B3,93,5C,B4,C5,BB,0D,69,8C,EB,29,4F,72,B9,80,42,EB,96,52,D6,4D,50,C0,F9,E3,DB,81,D3,3C,50,D6,F1,C9,36,C0,A3,A8,01,70,A2,BA,D8,FF,F6,FB,9B,5F,
    9. 17,13,25,92,53,28,CE,19,6F,F7,34,B0,91,23,3C,38,5E,CC,53,F5,5F,64,FA,F9,A9,BE,81,E0,BD,68,12,BE,AD,3B,F2,56,80,30,04,8D,D8,76,8F,1E,D2,C1,40,8E,2E,E4,73,63,
    10. B0,A2,AE,91,C5,C1,6E,35,6A,61,27,85,4A,8C,86,07,26,0E,F9,02,7A,87,71,33,5E,BE,67,C0,AA,38,1D,72,5D,0A,26,1E,40,EB,28,64,C6,8D,E1,9C,37,2E,68,0E,0D,6A,B5,61,
    11. 9F,53,64,57,FC,C3,B6,B7,1A,F1,D9,8A,30,43,69,89,60,63,36,D7,99,95,48,EC,BC,48,20,D1,FD,EA,41,93,8D,01,EF,F2,76,78,37,59,C6,36,2F,13,EF,F6,7F,BB,6E,52,20,F4,
    12. AB,20,64,5B,20,02,37,BA,BE,39,A4,7F,8C,BA,9B,6C,92,84,F1,8F,F5,30,A8,75,63,CA,71,9B,B1,DF,6F,25,C3,D7,3E,D2,AD,85,34,30,17,FD,E6,0C,E6,A6,EE,2D,19,90,EC,42,
    13. F0,07,CB,18,54,68,46,10,73,33,AA,D1,AB,62,DD,3A,A9,F9,9F,9A,D2,DF,10,24,E1,EC,72,9D,D2,43,31,58,00,E2,20,64,8A,77,06,04,FA,75,59,5F,29,68,49,79,5D,86,01,62,
    14. B5,86,29,AE,C7,B5,AF,24,87,46,C7,BB,6B,E9,30,C2,CC,A0,B9,5E,90,CE,05,39,06,91,8B,79,11,52,E0,EF,89,9B,39,91,DE,28,2C,2B,FE,40,B6,51,79,46,82,98,E3,8B,68,06,
    15. 7B,66,35,C6,09,87,AA,20,0D,88,C7,A9,15,C5,49,B7,6F,6E,71,18,00,DA,07,04,74,1E,9F,4F,98,DF,1B,E3,03,64,71,6E,FC,EF,AE,58,98,4E,3B,F8,23,AD,5F,07,C1,AE,06,55,
    16. 55,BC,C1,BA,A2,9C,0D,50,B1,44,D8,DF,72,F1,41,99,A5,74,A0,08,FB,CC,C6,44,79,FA,86,69,1E,11,74,48,C5,8D,EC,5D,4D,E5,56,02,F6,64,A9,E1,0E,34,2E,AF,CE,BC,87,18,
    17. 7F,2C,EF,F5,E0,55,C3,C5,CC,BF,42,5B,18,F5,91,D4,BB,24,01,CC,31,E4,95,D2,21,56,BF,18,3D,6F,6B,6F,69,93,3E,73,20,66,20,03,14,DF,F8,F5,15,9E,B6,07,34,7F,97,18,
    18. 28,6F,A4,98,F1,7E,7D,3D,BB,36,54,F7,04,2B,3C,27,01,D4,A4,0C,3E,99,1E,7D,86,2D,66,DE,02,1E,9F,4D,A4,AB,DF,1C,C7,D5,EE,84,0F,B9,4B,97,97,1C,70,77,4B,48,57,C6,
    19. 92,17,3D,5D,31,4D,A6,41,6C,2A,A1,D2,6D,40,4D,46,EA,83,9C,56,03,9F,57,37,69,8E,63,CC,C5,69,42,1A,58,7E,DC,FC,DE,A4,80,18,B9,CB,26,11,4B,D7,F7,FF,A4,AF,0F,1C,
    20. 5D,90,81,BF,C3,A8,9B,8F,39,E0,6C,F0,D7,F9,84,C2,57,DA,FB,4B,32,28,B5,71,06,18,E3,2D,3B,81,CD,3C,E6,36,D0,18,ED,92,A2,26,6D,54,DE,31,58,AD,BC,17,63,98,1F,C2,
    21. 1F,6A,D6,5A,65,AA,1B,B9,F8,22,60,20,66,36,4C,28,2F,75,00,FB,29,6E,9E,C3,23,C5,0C,63,C9,86,F5,66,C8,B8,11,34,32,36,A7,8C,23,BA,50,2E,A5,3B,FD,D8,D1,79,3B,74,
    22. 37,D6,B6,90,80,67,FC,0E,52,4B,84,1D,74,3B,EF,68,33,63,8D,8D,04,70,23,D0,6A,EB,EC,11,1A,C5,DD,FB,5E,33,2D,7F,B7,BC,15,80,C6,8F,D5,D0,6C,1B,F7,5C,31,DA,D7,A3,
    23. E2,6D,63,6D,7E,EE,20,B9,54,82,6E,F7,65,2D,0C,77,0F,EB,DE,22,ED,FC,EE,68,F9,7F,B2,79,F3,42,8D,B8,07,D9,97,6C,AA,ED,A1,B9,C5,D7,74,D0,15,6D,5A,62,D1,1C,E0,5A,
    24. 8E,38,D9,CB,61,8F,A6,27,43,44,B5,B3,B9,DB,48,37,B4,90,78,FA,B5,ED,79,ED,36,9B,1F,27,46,79,A1,91,73,EB,9E,E3,EC,75,5D,CF,E7,88,59,7B,41,9B,FD,35,64,7E,AC,63,
    25. 6E,EB,04,B8,90,5F,64,AE,B3,27,AB,30,62,BE,43,96,E4,56,5F,D7,A8,B5,80,FA,E7,42,3E,CE,84,60,45,DB,37,FA,9E,98,EA,5F,30,DF,63,51,86,9D,24,58,D2,CE,8F,5D,32,A9,
    26. 4E,73,33,17,F2,F8,94,6A,DA,DD,4C,4C,57,42,CD,F5,0D,46,8B,A2,9D,1D,B8,42,81,63,52,72,37,AF,60,AB,A1,6C,79,BA,AC,E4,85,71,30,9E,C8,9D,17,EA,1C,38,C2,BA,7D,DF,
    27. A8,B3,CB,86,40,84,CC,6A,22,77,71,47,69,45,5A,CB,5B,2F,9B,4B,4C,4A,C1,B6,BF,1B,10,C7,CF,63,0F,7E,CD,3C,47,D0,2B,65,47,9E,98,DB,EB,E4,6D,A9,DE,33,48,00,5E,61,
    28. F6,8A,3F,7F,97,FC,33,0B,FC,EB,48,67,54,E0,B2,8A,08,AE,CB,F6,E3,03,58,E9,76,3E,0E,D8,BB,80,55,19,F8,06,4B,E0,E6,B6,0C,6C,13,F7,31,82,85,C6,96,1B,A0,07,61,5A,
    29. 4A,18,3F,C0,4C,AC,F1,A3,FB,D7,08,DC,19,65,EC,C1,F6,70,23,53,DA,32,D0,B8,A7,17,7A,EB,BB,16,0F,B2,14,42,29,D0,B7,9C,8F,7C,52,2C,FF,13,20,50,2B,0A,0D,53,01,26,
    30. 1B,41,2F,EF,04,FA,E7,62,21,86,DF,E6,8A,A8,9D,81,7F,B6,F1,4C,06,A7,C3,24,D6,6E,0E,A3,74,87,2D,4E,9C,CF,56,10,E2,98,64,E8,99,FD,D9,DE,F4,73,23,3B,6B,A1,1E,F9,
    31. 60,72,DB,79,03,68,A0,74,73,33,2F,34,26,82,4B,04,8A,19,79,E5,EC,23,04,82,9A,CA,43,66,44,06,1E,6D,A8,B2,CF,78,6F,E5,E6,65,51,7F,90,3F,80,02,18,B1,44,A4,AE,C1,
    32. E2,A2,68,BB,C3,D6,86,6A,D2,8C,FA,8E,26,92,28,8B,E1,8E,EA,5F,58,94,D7,D6,74,F8,C5,01,58,61,8C,E4,43,1F,0D,6F,B8,BF,73,B0,DD,DC,B9,46,22,38,6D,19,22,0B,B3,48,
    33. CE,9A,8C,63,C8,0C,58,DB,0D,79,9A,B6,D7,45,FC,87,C2,AC,93,9E,2D,9D,63,7C,E3,CC,26,8A,FB,03,49,0A,FC,B8,38,4D,45,E5,DB,26,AC,14,60,A0,66,B9,3C,EC,27,C5,6C,9D,
    34. 89,78,01,18,B2,77,DB,45,31,1E,B5,8B,2A,17,62,FC,B3,2C,55,CC,7D,59,67,08,B7,26,D5,84,2F,34,88,16,BB,15,9A,01,D7,60,15,B4,8F,05,FE,B5,A0,DF,92,D8,DA,88,CF,B4,
    35. C8,71,36,57,93,32,D0,39,24,1E,6F,6F,89,1B,36,21,9A,B1,5B,3E,DC,60,2C,6E,A5,37,50,49,81,A2,50,C6,D5,84,56,F6,C2,85,34,F2,4C,AE,A7,12,BC,33,DD,5F,42,8F,36,4B,
    36. DF,D6,48,A0,82,47,25,B7,72,21,E0,EA,EB,B9,4D,4B,0C,C8,09,97,F1,09,BA,65,1C,04,98,A3,19,24,2D,43,61,10,58,32,80,38,98,8A,73,AE,87,08,54,38,A5,C0,39,A3,57,0F,
    37. 59,5A,30,D2,70,37,6E,D5,65,98,C8,8F,2A,B6,67,0C,E5,32,32,2A,4D,F1,4E,08,56,2A,E5,BC,10,BD,27,44,CC,C7,8F,BF,82,73,68,DE,6F,13,8F,95,02,6F,7A,16,F9,5C,79,FF,
    38. C8,91,3C,D2,3A,B7,96,A7,5A,BF,80,1D,94,78,61,96,18,61,8D,A4,7F,BC,0B,BE,B1,E3,9B,38,06,DF,F7,72,AB,37,5A,4F,48,06,3F,E8,DF,50,6B,82,F8,96,2D,BE,FB,A8,E5,10,
    39. DD,BB,C3,72,FE,BB,D1,5A,52,E3,34,E9,C0,8A,AF,65,C7,40,68,E9,67,19,EF,5B,3F,49,7C,9F,F3,F1,78,0A,D0,39,3F,1A,B3,9F,25,64,26,8F,B7,CD,CD,33,43,FD,01,8C,9A,11,
    40. BA,C2,14,90,B2,B8,D5,A1,C7,E4,4F,7B,A1,5E,08,1C,96,36,9D,3E,CA,0B,08,87,9B,D9,1E,00,3C,13,5B,C8,9F,F2,E2,0A,99,0C,C0,2C,41,28,71,49,99,51,A5,E2,70,29,44,D0,
    41. 86,80,AF,7D,F2,25,49,54,C1,FC,36,76,E0,51,62,AF,3C,6C,C5,A8,27,66,E6,5E,FE,3B,9E,D2,08,1F,1F,03,A2,16,34,19,99,BF,CB,E3,D8,70,B0,83,43,88,9B,68,E2,01,6D,7D,
    42. 42,45,B7,A0,18,43,7C,56,28,C1,38,BD,65,F4,20,C2,5A,4E,AC,93,C8,97,53,58,91,3F,95,1E,D4,F3,3F,13,5A,6E,EB,F9,31,92,C6,D5,96,B7,96,E7,19,43,FB,DF,FB,7A,F4,4E,
    43. DB,98,A6,5B,91,1D,59,B7,5B,69,C4,D3,37,88,8A,50,8F,4F,04,B7,1B,A8,41,6A,04,2A,4B,DA,45,ED,AC,FB,57,9C,31,F5,0D,CB,EE,1D,BD,8B,82,23,A0,3C,9D,8C,7B,A3,BF,63,
    44. 7F,3D,42,2C,6E,D2,9A,1A,00,4C,DC,82,85,CA,7D,8E,CB,F1,5C,36,42,82,03,6C,5E,32,2A,97,3D,B6,7D,43,8A,1D,A0,17,A1,62,6F,07,F4,42,8A,CB,AD,4B,11,8F,95,36,AC,EC,
    45. 34,76,CF,17,3A,11,3C,58,1D,AF,C9,BE,04,F0,63,12,E4,03,53,09,E8,75,C0,BD,17,46,75,5E,31,42,E5,25,D9,8E,6C,8A,F9,82,D8,B7,63,B6,28,3C,B4,60,94,04,7E,DD,CD,88,
    46. A6,8D,85,42,0A,E4,32,65,67,BE,0F,CB,7B,F3,64,2F,66,2C,08,9C,56,F5,24,25,63,13,39,D7,B8,17,65,EC,F4,33,E2,41,D0,4D,CF,0B,01,52,33,C5,60,CD,3F,6D,48,B8,D3,EF,
    47. 3F,91,44,E2,D9,B1,5D,72,DA,DA,A3,9D,9B,0F,DD,A3,AF,A8,D4,B7,C5,A5,58,FB,D0,43,83,AB,66,CD,42,98,66,B5,10,D9,DE,E3,05,BD,2C,4D,10,04,63,C8,81,4E,F0,1D,CA,D3,
    48. 7D,60,86,55,15,7D,BA,53,89,14,5B,80,13,87,11,73,3A,51,3B,A0,F5,99,33,87,13,06,D3,2B,DA,D6,38,C6,EF,2A,C5,BB,76,A4,6B,CC,79,34,28,8D,8E,2F,CE,18,B4,A2,06,03,
    49. 7F,E5,94,8F,75,73,DD,22,B7,F8,A6,F8,E4,AC,1E,15,3A,E0,1F,7E,FE,D6,B1,A8,1E,D6,D0,31,16,7E,6F,CE,10,5A,BC,85,4F,B5,A6,1C,CD,AE,9C,D1,23,8E,98,4B,AA,58,5D,D1,
    50. E0,A2,FD,BA,0D,A4,9D,24,26,8F,7C,E9,F1,20,32,CF,6A,74,36,FF,66,1E,A3,B9,76,77,3C,45,0E,35,AD,2D,E6,3F,14,A9,A1,C0,BF,5B,AD,7A,37,3C,6A,5E,7E,D7,8E,59,96,B5,
    51. 3F,85,D6,2B,43,E3,BA,BD,10,33,E3,36,09,5D,6A,DB,AE,EF,6E,DC,C0,B7,5B,87,A6,90,6C,BC,10,7C,6F,A1,DA,F3,C9,96,33,7B,B9,6C,FE,79,E1,D1,78,47,02,0F,1C,86,07,F7,
    52. 1D,FD,B2,47,5D,CB,E3,25,B0,4C,34,F8,25,61,CE,D3,D2,DF,0B,3D,74,9B,36,E2,55,C4,92,89,73,76,9D,46,DE,8B,95,F1,62,B5,3C,D6,66,CA,D9,AE,14,5E,7F,CF,BA,97,91,9F,
    Вот код, который ее вычисляет и проверяет условие (A)*(A^-1)=E
    модифицированный метод Жордана-Гаусса с поиском нечетных элементов "во главе" строки, описанный выше valterg-ом в посте №10.
    Массив инверсных значений также позаимствован из аттача valterg-а (четные элементы массива никогда не используются, поэтому установлены в качестве комментариев).

    Код (Text):
    1. const INVERSE:array[0..255] of byte=
    2.      (1,1,  3,171,  5,205,  7,183,  9,57,  11,163,  13,197,  15,239,  17,241,  19,27,  21,61,  23,167,
    3.      25,41,  27,19,  29,53,  31,223,  33,225,  35,139,  37,173,  39,151,  41,25,  43,131,  45,165,
    4.      47,207,  49,209,  51,251,  53,29,  55,135,  57,9,  59,243,  61,21,  63,191,  65,193,  67,107,
    5.      69,141,  71,119,  73,249,  75,99,  77,133,  79,175,  81,177,  83,219,  85,253,  87,103,  89,233,
    6.      91,211,  93,245,  95,159,  97,161,  99,75,  101,109,  103,87,  105,217,  107,67,  109,101,  111,143,
    7.      113,145,  115,187,  117,221,  119,71,  121,201,  123,179,  125,213,  127,127,
    8.      129,129,  131,43,  133,77,  135,55,  137,185,  139,35,  141,69,  143,111,  145,113,  147,155,
    9.      149,189,  151,39,  153,169,  155,147,  157,181,  159,95,  161,97,  163,11,  165,45,  167,23,
    10.      169,153,  171,3,  173,37,  175,79,  177,81,  179,123,  181,157,  183,7,  185,137,  187,115,
    11.      189,149,  191,63,  193,65,  195,235,  197,13,  199,247,  201,121,  203,227,  205,5,  207,47,
    12.      209,49,  211,91,  213,125,  215,231,  217,105,  219,83,  221,117,  223,31,  225,33,  227,203,
    13.      229,237,  231,215,  233,89,  235,195,  237,229,  239,15,  241,17,  243,59,  245,93,  247,199,
    14.      249,73,  251,51,  253,85,  255,255);
    15.  
    16. type TMatrix=array [0..51,0..51] of byte;
    17.      TVector=array [0..51] of byte;
    18.  
    19. procedure DisplayMatrix(matrix:TMatrix; memo:TMemo);
    20. var x,y:integer; s:string;
    21. begin
    22. for y:=0 to 51 do
    23.     begin
    24.     s:='';
    25.     for x:=0 to 51 do
    26.         s:=s+IntToHex(matrix[y,x],2)+',';
    27.     memo.Lines.Add(s)
    28.     end;
    29. end;
    30.  
    31. procedure TForm1.Button1Click(Sender: TObject);
    32. var k,x,y,YMain,YOdd,YCheck,XCheck,v,i:integer;
    33.     f:system.file;
    34.     xsrc,src,eq,check:TMatrix;
    35.     bTmp,bDivisor,bMultiplier,bRowMultiplier:byte;
    36.     sError,s:string;
    37.     vector:TVector;
    38. begin
    39. AssignFile(f,'..\table2.bin');reset(f,1);blockread(f,src,sizeof(src),k);closefile(f);
    40. AssignFile(f,'..\key_chack');reset(f,1);blockread(f,vector,sizeof(vector),k);closefile(f);
    41. FillChar(eq,sizeof(eq),0);
    42. for x:=0 to 51 do
    43.     eq[x,x]:=1;
    44. xsrc:=src;
    45. DisplayMatrix(src,Memo1);
    46. YMain:=0;
    47. repeat
    48.   LogMemo.Lines.Add('Starting row #'+IntToStr(YMain));
    49.   YOdd:=YMain;
    50.   while (src[YOdd,YMain] mod 2 = 0) and (YOdd<51) do inc(YOdd);
    51.   if (src[YOdd,YMain] mod 2 = 0) then
    52.      sError:='Invertible start of row not found'
    53.                                  else
    54.      begin
    55.      LogMemo.Lines.Add('Choosing row #'+IntToStr(YOdd)+' as invertible-starting');
    56.      if YOdd<>YMain then
    57.         begin
    58.         LogMemo.Lines.Add('Swapping rows #'+IntToStr(YMain)+' and #'+IntToStr(YOdd));
    59.         for x:=0 to 51 do
    60.             begin
    61.             bTmp:=src[YMain,x]; src[YMain,x]:=src[YOdd,x]; src[YOdd,x]:=bTmp;
    62.             bTmp:=eq[YMain,x];  eq[YMain,x]:=eq[YOdd,x];   eq[YOdd,x]:=bTmp;
    63.             end;
    64.         end;
    65.      bDivisor:=src[YMain,YMain];
    66.      bMultiplier:=INVERSE[bDivisor];
    67.      LogMemo.Lines.Add('Dividing row #'+IntToStr(YMain)+' /'+IntToStr(bDivisor)+' (multiplying *'+IntToStr(bMultiplier)+')');
    68.      for x:=0 to 51 do
    69.          begin
    70.          src[YMain,x]:=(integer(src[YMain,x])*bMultiplier) mod 256;
    71.          eq[YMain,x]:=(integer(eq[YMain,x])*bMultiplier) mod 256;
    72.          end;
    73.      LogMemo.Lines.Add('Subtracting this from all rows');
    74.      for y:=0 to 51 do
    75.          if y<>YMain then
    76.             begin
    77.             bRowMultiplier:=src[y,YMain];
    78.             for x:=0 to 51 do
    79.                 begin
    80.                 src[y,x]:=(integer(src[y,x])+256-((src[YMain,x]*bRowMultiplier) mod 256)) mod 256;
    81.                 eq[y,x] :=(integer(eq[y,x]) +256-((eq [YMain,x]*bRowMultiplier) mod 256)) mod 256;
    82.                 end;
    83.             end;
    84.      end;
    85.   inc(YMain)
    86. until (YMain=52) or (sError<>'');
    87.  
    88. for YCheck:=0 to 51 do
    89.     for XCheck:=0 to 51 do
    90.         begin
    91.         v:=0;
    92.         for i:=0 to 51 do
    93.             v:=v+xsrc[i,XCheck]*eq[YCheck,i];
    94.         check[YCheck,XCheck]:=v mod 256;
    95.         end;
    96.  
    97. s:='';
    98. for x:=0 to 51 do
    99.     begin
    100.     v:=0;
    101.     for i:=0 to 51 do
    102.         v:=v+eq[i,x]*vector[i];
    103.     s:=s+chr(v mod 256)
    104.     end;
    105. LogMemo.Lines.Add(s);
    106.  
    107. DisplayMatrix(src,Memo2);
    108. DisplayMatrix(eq,Memo3);
    109. DisplayMatrix(check,Memo4);
    110. end;
    А вот перемножение ее на вектор "key_chack" осымсленного результата не дает. Может быть дело именно в том, что в "полном алгоритме" два матричных умножения ?
     
  8. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    h0t
    Ищем нечетное число в строке, переставляем на диагональ, умножаем на обратное всю строку, очищаем столбец и в конце получим треугольную матрицу. Потом получим решение. Наверняка матрица там подобранная. Возможно придется при затыке возвращатся назад и выбирать другой элемент
     
  9. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    Матрицу получаем сразу единичную, а не треугольную. Матрица действительно подобранная, т.к. имеет обратную к себе.
    Затыков не обнаружилось - я тоже их боялся, но решилось всё за один проход.
     
  10. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    OLS
    Дельфи это хорошо. Теперь добьем :) Завтра или на днях. С матрицей раберемся. А вот с полной задачей да. Что там реально есть, сколько прогонов этого умножения и что еще в довесок.
     
  11. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    не все элементы кольца 256 обратимы!!!!!!
    Есть алгоритм Эрмита для этого!
     
  12. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Aids и другие
    Защиту от Олли WinDbg и IDA - нашел. На входе проверяется наличие окон с их классами и класс фантома. И при каждом клике на кнопочки.
    Исследуемая программа проверяет 3 пароля. При проверке 1-го пароля считается CRC32 от двух декодирующих функций завернутых в base64 и CRC32 от введенной строки и потом что-то там считается. Эта проверка легко обходится и переходим на проверку 2-го пароля. Попасть на проверку не получилось - отлаживал shadow с отключенным фантомом и нарвался на ошибку доступа по адресу 402170. Судя по дизассемблеру там используется два умножения на матрицу и что-то добавляется еще между умножениями. Все это запускается в отдельной нити(thread) и какие-то манипуляции с защитой памяти VirtualProtect... Дальше желания особого нет, т.к. ТС почти ничего не делает и советы ему бесполезно давать. Он ничего не сказал про первый пароль, не сказал обошел он его или нет. Сидит и ждет чего-то.
    Обращение матрицы проверил. Там только можно ошибится перепутав строки и столбцы - в остальном работает.
     
  13. Aids

    Aids New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2007
    Сообщения:
    275
    valterg
    Она снимается установкой доступа (execute read write) в олли или пропатчиванием доступа(PE хидера) в соответствующей секции.
    это установка хука на функцию Sleep, похученая функция проверяет отлаживается программа или нет функцией NtSetDebugFilterState, и если программа отлаживается то искажается выходной ключ.
    M=(D*K1+K2)*K3
    где K1 - матрица 52x52
    K2- матрица 1x52
    K3 - матрица 52x52
    D - 1x52 входное сообщение(неизвестное надо найти)
    M - 1x52 выходное
     
  14. Aids

    Aids New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2007
    Сообщения:
    275
    Пароль я первый нашёл. Расшифровав base64 и выполнив скрипт в котором и пароль
    Throughout the galaxy, thousands of Jedi
     
  15. Aids

    Aids New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2007
    Сообщения:
    275
    А то что я не отвечал, так пробовал вчера все ваши советы реализовать в коде.
    gorodon
    пробовал по совету заменить деление умножением в алгоритме #15 по таблице приложеной в аттаче. Получил почти обратную если проверить по формуле A*A^-1=E, на диагонали почти все еденицы и по бокам нули(тоже почти все). Вообщем считать надо подругому.

    Потом появился код отOLSя его вчера только перевёл на Cи но допустил какие то ошибки. Сейчас ставлю Дельфи что бы понять где накосячил. Так что у меня пока нет результатов расчёта.

    Кстати умножение в крякми идёт строка на строку, я этого сначала не заметил.
     
  16. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    Приложи С-шный код. Попробую увидеть неточность ...
     
  17. Aids

    Aids New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2007
    Сообщения:
    275
    Код (Text):
    1. unsigned char* loadinverse(char* fname){
    2.     unsigned char *INVERSE=new unsigned char[256];
    3.     memset(INVERSE,0,256);
    4.     FILE *f=fopen(fname,"r");
    5.     unsigned long id,value;
    6.     while(!feof(f)){
    7.         fscanf(f,"%u",&id);
    8.         fscanf(f,"%u",&value);
    9.         INVERSE[id]=value;
    10.     }
    11.     fclose(f);
    12.     return INVERSE;
    13. }
    14.  
    15.  
    16. unsigned char** obr_gaus(int n,unsigned char **src){
    17.     int k,x,y,YMain,YOdd,YCheck,XCheck,v,i;
    18.     unsigned char **eq,**xsrc;
    19.     unsigned char bTmp,bDivisor,bMultiplier,bRowMultiplier;
    20.     unsigned char *INVERSE;
    21.     INVERSE=loadinverse("D:\\Temp\\1\\matr256.txt");
    22.     int sError=0;
    23.     eq=new unsigned char*[n];
    24.     xsrc=new unsigned char*[n];
    25.     for (int i=0;i<n;i++){
    26.         eq[i]=new unsigned char[n];
    27.         xsrc[i]=new unsigned char[n];
    28.         memset(eq[i],0,n*sizeof(unsigned char));
    29.     }
    30.     for (int i=0;i<n;i++) eq[i][i]=1;
    31.     //savefile("D:\\temp\\1\\test.txt",n,eq);
    32.     for (int i=0;i<n;i++)
    33.         for (int j=0;j<n;j++) xsrc[i][j]=src[i][j];
    34.     YMain=0;
    35.     do{
    36.         YOdd=YMain;
    37.         while ((src[YOdd][YMain]%2 == 0)&&(YOdd<(n-1))) YOdd++;
    38.         if (src[YOdd][YMain]%2 == 0) sError=1;
    39.         else{
    40.              if (YOdd!=YMain){
    41.                 for (int x=0;x<n;x++){
    42.                     bTmp=src[YMain][x]; src[YMain][x]=src[YOdd][x]; src[YOdd][x]=bTmp;
    43.                     bTmp=eq[YMain][x];  eq[YMain][x]=eq[YOdd][x];   eq[YOdd][x]=bTmp;
    44.                 }
    45.              }
    46.              bDivisor=src[YMain][YMain];
    47.              bMultiplier=INVERSE[bDivisor];
    48.              for (int x=0;x<n;x++){
    49.                  src[YMain][x]=(((int)(src[YMain][x]))*bMultiplier) % 256;
    50.                  eq[YMain][x]=(((int)(eq[YMain][x]))*bMultiplier) % 256;
    51.              }
    52.              for (int y=0;y<n;y++)
    53.                  if (y!=YMain){
    54.                     bRowMultiplier=src[y][YMain];
    55.                     for (int x=0;x<n;x++){
    56.                         src[y][x]=(((int)(src[y,x]))+256-((src[YMain][x]*bRowMultiplier) % 256)) % 256;
    57.                         eq[y][x] =(((int)(eq[y,x])) +256-((eq [YMain][x]*bRowMultiplier) % 256)) % 256;
    58.                     }
    59.                  }
    60.         }
    61.         YMain++;
    62.     }while ((YMain<n) && (sError==0));
    63.     return src;
    64. }
    у меня есть ещё вот такая функция для получения обратных от деления по модулю
    Код (Text):
    1. void extended_euclid(long a,long b,long *x,long *y,long *d){
    2.     long q, r, x1, x2, y1, y2;
    3.     if (b == 0){
    4.         *d=a;
    5.         *x= 1;
    6.         *y= 0;
    7.         return ;
    8.     }
    9.  
    10.     x2= 1;
    11.     x1= 0;
    12.     y2= 0;
    13.     y1= 1;
    14.     while (b > 0){
    15.         q = a/ b; r = a - q * b;
    16.         *x = x2 - q * x1; *y = y2 - q * y1;
    17.         a = b; b = r;
    18.         x2 = x1; x1 = *x; y2 = y1; y1 = *y;
    19.     }
    20.  
    21.     *d = a; *x = x2; *y = y2;
    22.  
    23. }
    24.  
    25. long inverse(long a,long n){    //a- число n- 256
    26.       long  d, x, y;
    27.       extended_euclid(a, n, &x, &y, &d);
    28.       if (d == 1)  return x;
    29.       else return 0;
    30. }
     
  18. Aids

    Aids New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2007
    Сообщения:
    275
    OLS
    всё нашёл косяк с преобразованием типов накосячил
    Код (Text):
    1. src[y][x]=(((int)(src[y,x]))+256-((src[YMain][x]*bRowMultiplier) % 256)) % 256;
    а надо
    Код (Text):
    1. src[y][x]=((int)(src[y][x])+256-((src[YMain][x]*bRowMultiplier) % 256)) % 256;
    сейчас всё остальное попробую посчитать
     
  19. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    OLS,Aids в вашем коде вижу перестановку строк

    Код (Text):
    1.  
    2. ....
    3.        YOdd=YMain;
    4.         while ((src[YOdd][YMain]%2 == 0)&&(YOdd<(n-1))) YOdd++;
    5.         if (src[YOdd][YMain]%2 == 0) sError=1;
    6.         else{
    7.              if (YOdd!=YMain){
    8.                 for (int x=0;x<n;x++){
    9.                     bTmp=src[YMain][x]; src[YMain][x]=src[YOdd][x]; src[YOdd][x]=bTmp;
    10.                     bTmp=eq[YMain][x];  eq[YMain][x]=eq[YOdd][x];   eq[YOdd][x]=bTmp;
    11.                 }
    12. .....
    А где же обратная перестановка строк(после вычислений)? матрица же искажена...

    Лично я делал так - заводил массив Num[n]= {0,1,2,3,....n-1}
    В алгоритме везде к элемантам матрицы обращаюсь через элементы массива Num, т.е.

    Код (Text):
    1. src[Num[YMain]][Num[x]]
    При этом перестановка строк сводится к банальной перестановке соответствующих элементов в массиве Num....
    А результирующая матрица при этом НЕ искажается(!!!) т.е. не нужны доп-е перестановки строк.
     
  20. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    gorodon
    Не вижу искажения в перестановке строк. Это же не столбцы ... ?