Помогите решить задание
KSI1B 3E194 N*8GW ZC43U AG6FN 2RQB3 RG7AB 31EL2 Q724W *EGV9
91KBP 172NQ 8G101 2BDY6 *14QX 1QZES IN7WK 6QDMD GIMYW QSL*F
6FNQG OUTI2 UA8BI L*TXC 1ZBGW GGPGM CX2C9 B418X GS6IW *44WY
VC4SQ 1HXP1 777GK 4XG6T 1LNBW NV6V4 ZQKSI 1B3E1 94R9G XLVQC
*2VVB JGISW 7JT2X WYN60 *C8I1 QD7JB BDKTF C4CCP OWQQJ 1F4A*
143OV MHX*G 612QQ S26ID NGLHS F1ZZ2 WFASN XCSPO S24A8 HT0XI
LFF7D YTGOI Q*IH8 JNX1W FUDQ* 7JY3I GAGCG FKPI8 POIDU 32HGD
LFMV3 CQ0JI 6TNCG OPTCS 45IHF 5QCZ4 MR3N6 *BST3 7AOG6 L16G3
J9MVU KQILA QCGTF IXMBO SQXJG YJ02V LVTNX QQL3I ZI48H N7Z76
IGX1L 2XH1C Q0*94 R9GXM CCB27 3GVMK FGHPO GXLYV DXDL2 Q72BQ
KTC3J UTQ12 2GXK6 QXW92 IPIN7 WKJFA FLLR8 HX922 A8HT0 X7QLB
2SAVM HX*GG 4YW43 3*9A4 RKH87 BWSU6 YVT0T 41HNE XN3V3 59SC8
HGZDU LV3TQ 12L2C 5XXQ6 X4KQG W4TCQ GJY3I TL18I 25S2R *AMKF
GHPX2 Z4WCH JUXXW HOY2A VMGGD QRYRI Q23GV 6X*LH 623RQ LF8CM
TIWSO XQ*3W QV4QS IH81Q LV62E T0CIH 8OS77 AFUD0 LHQLB 2SAVM
HX**C S*CBG X62E6 *F21D 14Q6G 8YXRK FHZQ9 DL*F6 F08IM IN7WK
JI6TQ CI8*1 4QB*G 69QSE HDQIG 9G6QT 0XCU2 4ZSMB J53KP CSINZ
261CB SL2V8 OG7XX YBCBN 1ELHU TWNTY XFL22 DON26 75G6F 5IW9F
9IGX1 KEJKB XWIJU WBVZB N*ROE WTDXL UMHKQ TFZ*G FNPOX XG6MX
M*1TQ N*GE1 QD7MY N7Z2Y V44DQ GHBIT DULGV M*SHX F12O6 62EFJ
Q21ZO SB0V8 6N8FK XB32L VG6AM ZQIOH JQD7Y CBJ1P XHDW7 LOYBU
MKFGH IWBGL UVHTJ F4O7G GQ61Q UWN2C WINZM BFM7G 5QVUK QILAQ
CGM*S ILPQG 60YIC 4ZL4Z RO9DN V6GXD QX86T N*1JG UIL*T XB32L
NG6CN RIWO2 OGW6E 9XWLX 7WLHT L6JM7 41KRQ 2Q5M2 RVEGL 8RBRG
TBJVT 36KQE MV397 UWZBT 0T4QP A9W*A F6NKQ RBL17 D7HGG PZK48
HN7Z7 6IHFV LRBD8 WWKV6 BSG6H XB32L U3M7G 1LTX8 Q4WKV MHX*L
H8OJY S76IG 99G2D *GT*4 V8CX8 G6BH2 SWNNF GNL21 UYW5B 1U8CT
FIEHH NTMX6 FG4ZP X8BII G4*9* 4TQGO RWQ2X 1BHD9 GIULJ 2LE1K
CJKFX SPQCS 26FUR KTS8* JIG6G FV9TK QBCOS B0V86 N8FKX B32L7
AKHD9 GC8I2 7LLWY BF02V ZOXIX 2YB64 *QILH U7DJ6 2QF08 GHOI2
*VJFG X6Q7M 2T424 5*XNK 3KSOC IQK5Y 3JQFR XCW29 4TM39 92WSO
397UW ZBT0T 4YUN2 DYGLC KNMGO BOW22 5VET0 2KSY4 7LOJ9 V1NGX
HDJ2L E1KCJ KFXSH 2SWNN FGNL2 IO72Z TU*K6 MZKKW *NC*2 VVBJG
IGHOH QVKYM G9N26 XL4NG 6Y364 G*CLH 2SWNN FGNL2 8YBHQ VYVC4
SNQCM 2Q4QK T63J8 FW1LN 7Q05L BFZFJ Q*47L EYVKM KFGH4 MNQ*1
COXDC XLHO9 A1FC3 TVKKS I1B3E 1Y45Q *7SFY TB1U8 ENKNG YC4JG
4NTB1 DLR8H 2LWN6 QVXRK FQCWZ I1*FV T0XIL F397U WZBT0 T44IM
2L0FT CDTLR 8HB7X V6QD1 LGCMB 2QD7Y CBSZI KY234 VUIUC DKFQB
PGTI1 WKA4Z QGOPT 9276G *NK3H BKTN3 K3QX5 9GIUL NEQ61 8VS9Q
RQM3Z MAVIL GUFQB LO9*J 6QDGL JHB6I 2L2GK GX72G NBIT3 K3QX5
9GIUL IQZ7A PBTLJ RBRGT DL*YB 192K1 DOZ2K YMYNR KGH*C CB2J8
GX9MH Z7JYA 4AM6D TLR8H B7GVV MG99G HBKTN S162E 16KG6 CQGQJ
V6VGZ QKSI1 B3E1Y 4N*8G WZC43 UAQUS JFJLV T6QNG 6AG9* 7ZIN4
T21CO XDCXL HO92X GC6NK FQQBM NGQGL BJ1PX AOC9X 2TM3E *T1QL
C5M76 G3J1F R8*H7 L16G3 JL8IH MOIA1 6G3J0 QGOBT 9BUN3 B1KC7
HBCN3 TQKX4 S6IWH 2L23Q 6HMTL WZHN7 WKVLV SNLFX LJTS4 8*H1Q
C7HB1 WGULL EY0G6 XRJT2 X6Q3J NGP6O OSBUN 3B1KC 7HBCN 3TQKH
J8TF4 IN7WK NFTIL *2DIN IX1JQ UMTT4 14Q5G K1Y4M G1C8P N2W6E
YXDLC SX2NG GK6FA N4IWQ LB2SA VMHX* JCUUW Z9YYC C41LK MO1BD
U62E5 LQ28O 2B361 DEN*G CSC3L XK59H J8TF4 IN7WK EQAR9 GR8R3
4W3JY V1QGR BL17D 7H9VX EJXWB HZL6Q KHJ8T F4IN7 WK5LE MDL4M
O1WXL 1FADT KXWI2 CXXVV C1N9E Q2T57 UWFVD NQRL7 JIV36 QY19J
6QRC9 MKU6A G9*RB RGTDX 1CBR1 F2Q72 4T4W9 B1NQS 1R3Q* 156EF
ZJFU8 GQAXY V6M6Q 2DINI GX6VH DKLKM *1BDU VLAN* 8GWZC 43UAV
CS9GI H8N2D YVMD1 LZFXZ OI6NY UEDKG GXC3G 36QKU 6EB7W 7BWS2
V3D1L X7ZUT 260G
вот тут немного поменяли код, вернее добавили, чтоб легче было...
и ещё.. порядок знаков такой 0-9,A-Z,*
и зашифрованное сообщение на английском.
Вы единственный человек, которому дали такое задание?
Первое что пришло на мысль – дисковый шифратор 50-х гг.
Похоже разновидность полиалфавитного шифра или бирамный шифр.
"G" 5,463%
"Q" 4,848%
"2" 4,197%
"L" 4,016%
"X" 3,871%
"1" 3,618%
"6" 3,618%
"B" 3,546%
"N" 3,437%
"6/Q" 0,50651 %
"G/X" 0,50651 %
"2/L" 0,39797 %
"9/G" 0,39797 %
"B/3" 0,39797 %
"I/N" 0,39797 %
"L/2" 0,39797 %
"N/7" 0,39797 %
дана криптограмма 46386527581470372597605576960311681736335514231406949797 открытый ключ n=82500361.Восстановить сообщение.
И?)
А шифр?)
Самопальный алгоритм?)))
Всегда! :)
И?)
А шифр?)
Самопальный алгоритм?)))
Препод сказал можно решить как то!
Каждую букву исходного сообщения заменили её двухзначным порядковым номером(а-01,б-02....я-33) Полученную цифровую последовательность разбили(слева направо) на трёхзначные цифровые группы без пересечений и пропусков.Затем каждое из полученных трёхзначных чисел умножили на 77 и оставили только 3 последние цифры произведения.В результате получилась последовательность 317564404970017677550547850355
получается бред
Если знаем алгоритм тогда где-то так:
1. 317-564-404-970-017-677-550-547-850-355
2. По предложенному алгоритму получим:
121 332 252 610 221 801 150 111 050 615
3. Терь:
12 13 32 25 26 10 22 18 01 15 01 11 05 06 15
ключшифранайден
4. И того:
"ключ шифра найден"
спасибо большое! а что за алгоритм как называется как работает вообще? поясните пожалуйста!и по первой задаче может есть к ней какой алгоритм?
По первому заданию:
там понятно что асиметричный шифр, но без описания алгоритма браться не буду, так как мало ли какого творчества туда напихали.
Название? – ОСА
(Очередной Самопальный Алгоритм:) )
Его вы же и описали:
Или нужно как найти открытый текст?
Hint: 82500361 = 8893 x 9277 (произведение двух простых чисел).
Кому не лень, может попробовать подобрать e (скорее всего небольшое число: 3 или 17), по нему вычислить d= e-1 mod (p-1)(q-1). И посчитать Md mod n
Как получилась эта последовательность:121 332 252 610 221 801 150 111 050 615 Каким способом?Каким образом вообще?
Просто составил таблицу всех возможных значений и сделал поиск в ней :)
Тоесть,
000*77=000
001*77=001
.....
100*77=700
101*77=777
......
999(не может быть, но на всяк случай, мало ли)*77=923
И не лень же было :)
4 строки в программе :)
ну а всё таки задание с открытым ключом можно как нибудь решить? и если по этой формуле решать откуда там сообщение появится?
Чтобы рассчитать обратный множитель нужно использовать расширенный алгоритм Евклида. Появится число, а уж как там оно соотносится по кодировке с алфавитом — надо будет догадываться.
Так там же большое число получается по идее.Как быть?
По байтам посмотреть.
не могу сообразить.......ну помогите пожалуйста кто понимает и кому не трудно......
Влом
Ну плиззззззз! я до половины алгоритма дохожу, а дальше не понимаю! и вообще как Вы нашли числа р и q?
Ну кто нибудь отзовитесь!!!
а ты нарисуй так же красиво, как в теме про аутентификацию ;)
что нарисовать?
ЛЮЮЮЮДИИИИИ! отзовитесь! кто в этом шарит!
Так вы хоть задачу то уточните. Что получить надо? Исходные данные это текст или набор цифр. Было бы неплохо еслибы вы полностью задание описали.
дана криптограмма 46386527581470372597605576960311681736335514231406949797 открытый ключ n=82500361.Восстановить сообщение. Вот она вся задача! мысли то есть но как до конца довести не могу сообразить....
Вот вам на предыдущей странице уже написали что 82500361 = 8893 x 9277
тогда ф(n)=82482192. Число e- верятнее всего 3,5 или 17. 3 не подходит тк НОД(3,82482192)!=1.
Остается 5 или 17.
Для 5 d соответственно равно d=32992877
Для 17, d=14555681
Теперь что я могу вам предложить. Разбейте криптограмму на блоки по 8 цифр в каждом:
46386527 58147037 25976055 76960311 68173633 55142314 06949797
Ни один из блоков не больше n(хороший знак) а дальше возведя каждый из блоков в степень d по модулю n получите два варианта исходных текстов, из которых и будете выбирать.
если так, то получается при e=5 исходный текст будет 72895781 48931469 66238252 9789399 21285339 80439104 17876618
при e=17 текст 5887899 79868955 32784348 76369648 30961644 15373112 46887123
Такой ответ вас устраивает?
а как блок возвести в степень d по модулю n,т.е. блок умножаем на d и делим на n
как мы числа p и q подобрали? по какой формуле? или просто подбором?
В данном случае можно и подбором. Тупо перебираем все числа от 2 до n^1/2 на предмет делится ли на это число n.
это такой вялый троллинг чтоли?
я не понимаю о чем вы или о ком)))))объясните пожалуйста как это считается! учитывая что d в нашем случае – большое число!
Столбиком.
Покажите на моём примере пожалуйста!
чей-то пример уже разбирали[link1]
Факторизацией?
всё равно не получается d найти....(((( не могу понять эту модульную арифметику.....можно ещё более просто объяснить это?
и по идее должно получиться какое-то текстовое сообщение?
ЛЮЮЮДИИ! пожалуйста помогите!
завтра сдать нужно! в принципе за ответ спасибо но как это получилось не понятно!?
И на рассвете вперед, уходит рота солдат, Уходит чтоб победить, им помог деканат... и далее по тексту :) Кирзовые сапоги — это круто!
эх....деканат....деканат....ну всё таки поясните ещё раз про d!
пожалуйста!
Вы создали уже достаточно информационного шума. Если кто-то найдёт возможность, обязательно ответит, но если будете и дальше упорствовать, тему придётся закрыть.
Спасибо буду ждать кого-нибудь.....
А что вам непонятно? Как найти d? d, говоря математическим языком, это мультипликативно обратный элемент к e по модулю ф(n). Т.е. e*d=1 mod ф(n). Вам было дано n. Методом подбора вы нашли факторизацию n, числа p и q. Затем вычислили ф(n)=(p-1)*(q-1). Выбрали e. Обычно в качестве e выбирают число вида 2^n+1. Учитывая то, что в вашем случае пример явно демонстративный вы не без оснований предполагаете что e число маленькое, маленькие числа, удовлетворяющие условию e=2^+1, это 3, 5, 9, 17. Так же число e должно быть взаимно простым с числом ф(n), используя алгоритм Евклида вычисляете НОД(e, ф(n)), если НОД=1 значит числа взаимно простые. В вашем случае вы установили что таковыми являются 5 и 17. Теперь используя расширенный алгоритм Евклида вы находите обратные к 5 и 17. Это и будут числа d. Теперь вам остается только возвести криптотекст в степень d по модулю n. Обычно возведение числа в степень по модулю выполняется с помощью т.н. метода квадратов и умножений.
Алгоритм кстати, который здесь используется для шифрования, называется RSA.
Теперь, когда я вам расписал все основные этапы, можете сами погуглить что такое алгоритм Евклида или метод квадратов и умножений, RSA и асимметричная криптография вообще. Хотя лично вам, наверное, делать этого не стоит.:)
спасибо большое за столь конкретное пояснение,но ведь именно это мне и нужно считать!!!! в моём примере n=82500361 почему d=32992877
А в комменте выше уже предложили:
а то как-бы:
Может темы с однообразными задачками для студентов уже помещать в оффтопик?
Спасибо всем большое! додумать так и не получилось.....
Помогите полететь на Луну. Пробовал. Не получается. В Звёздный Городок не допускают. Очень прошу помочь.
Это так, навеяло :)
а не подскажете где можно посмотреть вопрос np-сложность в криптографии?
в гугле.
Например:
а есть ли к такой задаче какая-нибудь формула?
Есть.
Сi = (Pi * Ki) mod 1000.
Где, Кi = ключ = 77.
а pi-это последовательность из 3-х исходных цифр?
что значит по модулю 1000? как это считается?
как найти pi?
где я? зачем я здесь?
у меня дана последовательность цифр 317564404970017677550547850355 как из этой последовательности получилась 121332252.....с помощью формулы ci=(pi*ki)mod1000,где кi=77?
Я ж уже писал как получилась.
Просто воссоздал по формуле таблицу подставновки.
Что именно не ясно?
П.с.: смахивает на новомодный (старый забытый?))) метод троллинга.
Вот интересно, где и на каком курсе вы учитесь?) Просто чтобы знать куда не отдавать свое чадо ))))
Давно пора. А лучше вообще их закрывать.
то есть мы 121 угадать должны?
Нет, –
121 выбираем из таблицы, кoторую получаем по
В Windows-калькуляторе выберите "вид"-"инженерный", наберите <любое_число><mod><1000><=>
:)
Гость (01/12/2010 17:17), а скриншот? А лучше анимацию сделайте. Иначе, боюсь, дело с места не сдвинется.
Точно!
:D
А каким образом возводиться восьмизначное число в степень(число степени тоже восьмизначное) по модулю какого-нибудь тоже восьмизначного числа? то есть как с такими большими числами работать не прибегая к программированию?
Оптимальный способ вычисления карандашом на бумаге чтоль?
Если не нужна точность до бита – таблица логарифмов. Если нужна – изображаем компьютер на бумаге ("Процессор не обнаружен – программная эмуляция"©). Расписать число по битам. Возводим в квадрат и приводим по модулю. Если соответствующий бит единичный, умножаем накопитель на результат (естественно тоже сразу приводим по модулю). Если бит нулевой, снова возводим в квадрат и так далее. Вобщем, IEEE P1363 / D13 (Draft Version 13) рулит (если кто видел более поздний драфт в открытом доступе, бросьте пожалуйста ссылку).
а если взять конкретный пример 46386527 в степени 82482192 по модулю 82500361 например то как получится в итоге 72895781
Ну вот взял уже другой пример.
На бумажке можно считать и недвоичными, а десятичными полиномами:
Y = x7•107 + x6•106 + x5•105 + x4•104 + x3•103 + x2•102 + x1•101 + x0•100
M = 46386527 = 4•107 + 6•106 + 3•105 + 8•104 + 6•103 + 5•102 + 2•101 + 7•100
d = 32992877 = 3•107 + 2•106 + 9•105 + 9•104 + 2•103 + 8•102 + 7•101 + 7•100
n = 82500361 = 8•107 + 2•106 + 5•105 + 0•104 + 0•103 + 3•102 + 6•101 + 1•100
P = M d mod n
Сначала по цепочке рассчитаем все степени 46386527i mod 10 от 1 до 10 (итерация, умножение предыдущего результата на последующий) .
Дальше считаем 8 цифр ответа:
p8 = 1 #это не надо, т.к. коэффициенты 0-7
p7 = p810 • Md7 = 1 • 463865273 mod 10 = (46386527 – int ( 46386527 / 10) * 10 )3 mod 10 = 343 mod 10 = 3 mod 10
p6 = p710 • Md6 = 310 • (463865272) mod 10 = 310 mod 10 • (463865272) mod 10 = 9 mod 10 • 463865272 mod 10 = 9 mod 10 • 9 mod 10 = 1 mod 10
p5 = p610 • Md5 = 1 • 463865275 mod 10 = 7 mod 10, ну и т.д.:
p4 = p510 • Md4 = ...
p3 = p410 • Md3 = ...
p2 = p310 • Md2 = ...
p1 = p210 • Md1 = ...
p0 = p110 • Md0 = ...
P = p7p6p5p4p3p2p1p0 # — это какой-то LOL, а не wiki-форматирование коэффициентов ;-)
В процессе всё должно упрощаться и при подсчёте каждой последующей цифры можно подставлять расчитанные степени от предыдущей.
Да, там глючит, сам мучился. Ставьте лишние пробелы между множителями и будет счастие.