Sızan Kriptoqrafiya
ACM ICPC hakimləri problemlərin sızdırılmaması üçün çox diqqətlidirlər və bütün ünsiyyətləri şifrələyirlər. Lakin, bəzən zəif şifrləmə sxemlərindən istifadə edirlər. Budur, belə bir nümunə.
Seçilmiş şifrləmə çox sadə idi: girişin hər bir hissəsini paylaşılan açara uyğun olaraq bəzi bitləri dəyişdirərək şifrələmək. Məqbul təhlükəsizlik təmin etmək üçün həm hissənin, həm də açarın ölçüsü 32 bitdir.
Tutaq ki, giriş m 32-bit tam ədədlər ardıcıllığıdır:
N[1] N[2] N[3] ... N[m]
Açar K ilə kodlaşdırıldıqdan sonra bu, m 32-bit tam ədədlər ardıcıllığına çevrilir:
(N[1] ^ K) (N[2] ^ K) (N[3] ^ K) ... (N[m] ^ K)
burada a ^ b a və b-nin bitwise exklüziv və ya əməliyyatıdır.
Exklüziv və ya yalnız operandlarından biri 1 olduqda 1 olan, əks halda 0 olan məntiqi operatorudur. Budur, 1-bit tam ədədlər üçün onun tərifi.
Gördüyünüz kimi, bu, 2 modulu ilə toplama ilə eynidir. İki 32-bit tam ədəd a və b üçün onların bitwise exklüziv və ya a ^ b aşağıdakı kimi müəyyən edilir, onların 0 və 1-lərdən ibarət olan ikili təsvirlərindən istifadə etməklə.
a ^ b = a[31] ... a[1] a[0]^b[31] ... b[1] b[0] = c[31] ... c[1]c[0]
burada
Məsələn, ikili notasiya istifadə edərək, 11010110 ^ 01010101 = 10100011, və ya onaltılıq istifadə edərək, d6 ^ 55 = a3.
Bu cür şifrləmə statistik hücumlara qarşı zəif olduğu üçün, mesaj əvvəlcədən sıxılmalıdır ki, heç bir statistik müntəzəmliyi olmasın. Biz güman edirik ki, N[1] N[2] ... N[m] artıq sıxılmış formada.
Lakin, problem ondadır ki, sıxılma alqoritmi özü bəzi müntəzəmlik forması təqdim edir: sıxılmış məlumatın hər 8 tam ədədindən sonra, bu tam ədədlərin cəmini daxil edir. Yəni, yuxarıdakı girişdə,
N[9] = N[1] + ... + N[8],
burada toplama 2^32 modulu ilə aparılır.
Xoşbəxtlikdən, hakimlər arasında bir ünsiyyəti ələ keçirə bildiniz. Bəlkə də bu, final üçün bir problemdir!
Çox ağıllı olduğunuz üçün, açarın ən aşağı bitini, K[0] ilə göstərilən, asanlıqla tapa biləcəyinizi mütləq görmüsünüz. Bir tərəfdən, əgər K[0] = 1 olarsa, kodlaşdırıldıqdan sonra Σ1 ≤ i ≤ 8 N[i] ^ K-nin ən aşağı biti dəyişməz qalır, çünki K[0] cüt sayda əlavə olunur, lakin N9 ^ K-nin ən aşağı biti dəyişir, beləliklə onlar fərqlənməlidir. Digər tərəfdən, əgər K[0] = 0 olarsa, kodlaşdırıldıqdan sonra Σ1 ≤ i ≤ 8 N[i] ^ K-nin ən aşağı biti hələ də N[9]^K-nin ən aşağı bitinə bənzər olacaq, çünki onlar dəyişmir. Məsələn, kodlaşdırıldıqdan sonra ən aşağı bitlər 1 1 1 1 1 1 1 1 1 olarsa, K[0] mütləq 1 olmalıdır, lakin 1 1 1 1 1 1 1 0 1 olarsa, K[0] mütləq 0 olmalıdır.
İndiyə qədər yaxşıdır. Daha yaxşısını edə bilərsinizmi?
Siz kodlaşdırma üçün istifadə olunan açarı tapmalısınız.
Giriş
Giriş yalnız müsbət tam ədəd S olan bir sətirlə başlayır, bu, girişdəki datasetlərin sayını göstərir. S 1000-dən çox deyil.
Bunu S datasetlər izləyir. Hər bir dataset rabitənin ilk doqquz hissəsinə uyğun gələn doqquz 32-bit tam ədəddən ibarətdir. Onlar '0'-dan '9'-a qədər rəqəmlər və kiçik hərflər a-dan f-ə qədər istifadə edərək onaltılıq notasiya ilə yazılır və heç bir sıfırla başlamır. Onlar boşluq və ya yeni sətirlə ayrılır. Hər bir dataset yeni sətirlə bitir.
Çıxış
Hər bir dataset üçün kodlaşdırma üçün istifadə olunan açarı çıxarmalısınız. Hər bir açar öz sətirində tək görünməlidir və '0'-dan '9'-a qədər rəqəmlər və kiçik hərflər a-dan f-ə qədər istifadə edərək onaltılıq notasiya ilə yazılmalıdır və heç bir sıfırla başlamamalıdır.