شرح بالتفصيل أخطر برنامج لاختراق هواتف الأندرويد

Classical Cryptography - Arabic Book  التشفير الكلاسيكى 2

ھﻞ 101 ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ . 2 ﻻ

ھﻞ 101 ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ 3 ، ﻻ

ھﻞ 101 ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ 4 و5 و 6و 7 و8 و . 9 إﻟﻰ أن ﻧﺼﻞ إﻟﻰ 10 ، وأﯾﻀﺎ ﻻ ﯾﻘﺒﻞ ، اذا اﻟﻨﺘﯿﺠﺔ أن اﻟﻌﺪد 101 ھﻮ ﻋﺪد أوﻟﻲ .

ھﺬه اﻟﻄﺮﯾﻘﮫ ﻓﻲ اﻟﺒﺤﺚ ﻟﯿﺴﺖ ﻣﻦ أﻓﻀﻞ اﻟﻄﺮق ﻓﻲ اﺧﺘﺒﺎر أوﻟﯿﮫ اﻟﻌﺪد ، وھﻨﺎك اﻟﻜﺜﯿﺮ ﻣﻦ اﻟﻄﺮق أﻓﻀﻞ ﻣﻨﮭﺎ ، وھﻲ ﺗﺴﻤﻰ ﻃﺮﯾﻘﮫ . Trial Division

ﻣﺜﻼ ﻟﺪﯾﻨﺎ ﻋﺪد ﺿﺨﻢ ﯾﺘﻜﻮن ﻣﻦ 500 ﺧﺎﻧﮫ ، ﺑﻌﺪ أﺧﺬ اﻟﺠﺬر اﻟﺘﺮﺑﯿﻌﻲ أﺻﺒﺢ ﯾﺘﻜﻮن ﻣﻦ 250 ﺧﺎﻧﮫ

، اﻵن ﻃﺮﯾﻘﮫ Trial Division ﺳﻮف ﺗﻜﻮن ﻣﻀﯿﻌﮫ ﻟﻠﻮﻗﺖ واﻟﺠﮭﺪ ﻷﻧﮭﺎ ﺳﻮف ﺗﺨﺘﺒﺮ ﻣﻦ اﻟﺒﺪاﯾﺔ وﺣﺘﻰ ذﻟﻚ اﻟﻌﺪد اﻟﺬي ﯾﺘﻜﻮن ﻣﻦ 250 ﺧﺎﻧﮫ ، ﻟﺬﻟﻚ ﻟﻠﺘﻌﺎﻣﻞ ﻣﻊ اﻷﻋﺪاد اﻟﻀﺨﻤﺔ (ﻛﻤﺎ ھﻮ اﻟﺤﺎل ﻓﻲ اﻟﺸﻔﺮات اﻟﺤﺪﯾﺜﺔ) ﯾﺠﺐ اﻟﺒﺤﺚ ﻋﻦ ﺣﻞ أﻛﺜﺮ ﻛﻔﺎﺋﮫ .

وھﻨﺎك اﻟﻜﺜﯿﺮ ﻣﻦ اﻟﻄﺮق ﻟﮭﺬا اﻷﻣﺮ ، وﺳﻮف ﻧﺘﻨﺎوﻟﮭﺎ ﻓﻲ اﻟﻨﺴﺨﺔ اﻟﻨﮭﺎﺋﯿﺔ ﻣﻦ اﻟﻜﺘﯿﺐ ﺑﺈذن اﷲ ﺑﺎﻟﺘﻔﺼﯿﻞ ، وﻟﻜﻦ ﯾﻤﻜﻦ ﻟﺘﺴﺮﯾﻊ اﻷﻣﺮ اﺧﺘﺒﺎر اﻷﻋﺪاد اﻟﻔﺮدﯾﺔ ﻓﻘﻂ ﻓﻲ ﻃﺮﯾﻘﮫ . Trial Division

أﯾﻀﺎ ھﻨﺎك ﻃﺮﯾﻘﮫ Sieve of Eratosthenes ، وھﻲ ﺗﻌﺘﻤﺪ ﻋﻠﻰ ﻋﻤﻞ إﻟﻐﺎء ﺟﻤﯿﻊ ﻣﻀﺎﻋﻔﺎت اﻷﻋﺪاد 2 و 3 و5 و7 ﻣﻦ ﻣﺪى اﻷﻋﺪاد اﻟﻤﺮاد اﻟﺒﺤﺚ .

ﻣﺜﺎل ﻟﻠﺘﻮﺿﯿﺢ ، ﻧﺮﯾﺪ ﻣﻌﺮﻓﮫ اﻷﻋﺪاد اﻷوﻟﯿﺔ ﺑﯿﻦ 2 إﻟﻰ 99 ، ﻧﻘﻮم ﺑﻌﻤﻞ ﺟﺪول ﻓﯿﮫ ﺟﻤﯿﻊ ﺗﻠﻚ اﻷﻋﺪاد (ﻓﻲ اﻟﻐﺎﻟﺐ ﯾﻜﻮن ﻓﻲ ﻣﺼﻔﻮﻓﺔ) ، ﺑﻌﺪھﺎ ﻧﻘﻮم ﺑﺸﻄﺐ ﻣﻀﺎﻋﻔﺎت اﻟﻌﺪد 2 ﻣﻦ اﻟﺠﺪول ، وﻣﻀﺎﻋﻔﺎت اﻟﻌﺪد 3 ﻣﻦ اﻟﺠﺪول وھﻜﺬا ، 

وھﻮ اﻵن ﯾﺤﺘﻮي ﻋﻠﻰ ﺟﻤﯿﻊ اﻷﻋﺪاد اﻷوﻟﯿﺔ ﻣﻦ 2 إﻟﻰ 99 ، ﻋﻠﻰ اﻟﻌﻤﻮم وﻛﻤﺎ ﻻﺣﻈﺖ أﻧﮭﺎ ﺳﻮف ﺗﺴﺘﻐﺮق ﻣﺴﺎﺣﮫ ﻛﺒﯿﺮة ﻓﻲ ﺣﺎﻟﮫ اﻟﻌﺪد اﻟﻤﺮاد اﺧﺘﺒﺎره ﻛﺒﯿﺮ ، ذﻟﻚ ھﻲ ﻏﯿﺮ ﻣﺴﺘﺨﺪﻣﮫ ﺑﻜﺜﺮة 

.

  ﺍﻟﻘﺎﺳﻢ ﺍﻟﻤﺸﺘﺮﻙ ﺍﻷﻋﻈﻢ Greatest Common Divisor (ﺍﺧﺘﺼﺎﺭﺍ

اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻌﺪدﯾﻦ ھﻮ أﻛﺒﺮ ﻋﺪد ﺻﺤﯿﺢ ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ اﻟﻌﺪدﯾﻦ .

ﻣﺜﻼ ﻧﺮﯾﺪ ﻣﻌﺮﻓﮫ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻛﺒﺮ ﻟﻠﻌﺪدﯾﻦ 30 ، . 18 ﻧﻘﻮم ﺑﻤﻌﺮﻓﮫ ﺟﻤﯿﻊ ﻗﻮاﺳﻢ اﻟﻌﺪدﯾﻦ ، وﻧﺄﺧﺬ اﻟﻌﺪد اﻷﻛﺒﺮ ﻣﻦ ھﺬه اﻟﻘﻮاﺳﻢ :

30ﯾﻘﺒﻞاﻟﻘﺴﻤﺔﻋﻠﻰ1و2و3و5و6و10و15و30

18ﯾﻘﺒﻞاﻟﻘﺴﻤﺔﻋﻠﻰ1و2و3و6و9و18

ﻧﻼﺣﻆ ﻓﻲ اﻷﻋﺪاد اﻟﺴﺎﺑﻘﺔ أﻛﺒﺮ ﻗﺎﺳﻢ ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ اﻟﻌﺪدﯾﻦ وھﻮ . 6

GCD(30,18) = 6

ﯾﻘﺎل ﻋﻦ ﻋﺪدﯾﻦ "أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ" Relatively Prime اذا ﻛﺎن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﮭﻢھﻮ.1

اﻷزواج اﻟﺘﺎﻟﯿﺔ ﻣﻦ اﻷﻋﺪاد أوﻟﯿﻨﺎ ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ : Relatively Prime

اﻷزواج اﻟﺘﺎﻟﯿﺔ ﻣﻦ اﻷﻋﺪاد أوﻟﯿﻨﺎ ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ : Relatively Prime

8 و 9 ، ﻷن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﮭﻢ ھﻮ . 1

 

23و44

 

27و55

 

اﻻﺷﺎره اﻟﺴﺎﻟﺒﺔ ﻻ ﺗﺆﺛﺮ ﻓﻲ ﺣﺴﺎب اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ :

 

GCD(x,y) = GCD(x,-y) = GCD(-x,y) = GCD(-x,-y) = GCD(|x|,|y|)

 

ﻣﺜﺎل 

GCD(18,-54) = GCD(18,54) = 9

 

ﻷﺧﺬ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻤﺠﻤﻮﻋﮫ ﻣﻦ اﻷﻋﺪاد ﻧﻘﻮم ﺑﺄﺧﺬ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻌﺪدﯾﻦ ﻣﻨﮭﻢ ، واﻟﻨﺎﺗﺞ ﻧﺄﺧﺬه ﻣﻊ اﻟﻌﺪد اﻟﺜﺎﻟﺚ وھﻜﺬا .

 

ﻣﺜﺎل : اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ل 20: و 30 و 15 ھﻮ 5 وذﻟﻚ :

 

GCD(20,30) = 10

CGD(10,15) = 5

 

اذا ﻛﺎن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻤﺠﻤﻮﻋﮫ ﻣﻦ اﻷﻋﺪاد 1 = ، وﻛﺎن ھﻨﺎك زوج ﻣﻦ ھﺬه اﻷﻋﺪاد (أي ﻋﺪدﯾﻦ) اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ھﻮ ﻏﯿﺮ ) 1أي ﻟﯿﺲ أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ) ، ﻓﺄﻧﮭﺎ ﺗﺴﻤﻰ mutually relatively prime ، أﻣﺎ ﻓﻲ ﺣﺎﻟﺔ ﻛﺎن ﺟﻤﯿﻊ اﻷزواج ﻣﻊ ﺑﻌﻀﮭﺎ ﯾﻜﻮن اﻟﻘﺎﺳﻢ ﯾﺴﺎوي واﺣﺪ ﻓﺈﻧﮭﺎ ﺗﺴﻤﻰ . pairwise relatively prime

 

ﻣﺜﺎل : ﻟﺤﺴﺎب اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻸﻋﺪاد 28 و 126 و 21 و : 10

 

=     ( (28,126) , 21 , 10)

=   (14 , 21 , 10)

=     ( (14,21) , 10)

 

=   (7,10)

=   1

ﻻﺣﻆ اﻟﻨﺘﯿﺠﺔ ھﻲ واﺣﺪ ، ﺑﺎﻟﺮﻏﻢ ﻣﻦ أن ھﻨﺎك زوج ﻣﻦ اﻷﻋﺪاد ﻏﯿﺮ أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ ، . 7 = (28,126)

وﻓﻲ ھﺬه اﻟﺤﺎﻟﺔ ﺗﺴﻤﻰ ﻣﺠﻤﻮﻋﮫ اﻷﻋﺪاد . mutually relatively prime أﻣﺎ ﻓﻲ ﺣﺎﻟﮫ ﻛﺎن ﺟﻤﯿﻊ اﻷزواج ﻣﻦ اﻷﻋﺪاد أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ ﻓﺘﺴﻤﻰ ﻣﺠﻤﻮﻋﮫ اﻷﻋﺪاد ﺑـ pairwise relatively . prime

ﻣﺜﺎل :اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك ﻟﻸﻋﺪاد 18 و 9 و 25 ھﻮ 1 ، وﻣﻊ ذﻟﻚ ﻓﮭﻲ mutually relatively prime ، ﻻن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ل 18,9 ھﻮ 9 (أي ھﻤﺎ ﻟﯿﺴﺎ أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ) .

ﺧﻮﺍﺭﺯﻣﻴﺔ ﺃﻗﻠﻴﺪﺱ Euclidean Algorithm

اذا ﻛﺎن ﻟﺪﯾﻨﺎ ﻋﺪدﯾﻦ c,q ﺑﺤﯿﺚ c = q*d + r ، اذا . GCD(d,r) = GCD(c,q )

اﻟﻘﺎﻋﺪة اﻟﺴﺎﺑﻘﺔ ﻣﮭﻤﺔ ﺟﺪا ، وﻧﺴﺘﻄﯿﻊ ﻣﻦ ﺧﻼﻟﮭﺎ إﯾﺠﺎد اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻠﻌﺪدﯾﻦ ﺑﺴﺮﻋﺔ .

ﻣﺜﺎل : أوﺟﺪ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ 132 و 55 ﺑﺎﺳﺘﺨﺪام ﺧﻮارزﻣﯿﺔ أﻗﻠﯿﺪس :

132=55*2+22

55 =22*2+11

22 =11*2+0

ﻧﺘﻮﻗﻒ ﻋﻨﺪ اﻟﻮﺻﻮل إﻟﻰ اﻟﺼﻔﺮ ، وﯾﻜﻮن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ھﻮ 11 وذﻟﻚ :

GCD(132,55) = GCD(55,22) = GCD(22,11) = GCD(11,0) = 11

ﻣﺜﺎل أﺧﺮ : أوﺟﺪ GCD(252,198) ﺑﺎﺳﺘﺨﺪام ﺧﻮارزﻣﯿﺔ أﻗﻠﯿﺪس ؟

252=198*1+54

198=54 *3+36

54 =36 *1+18

36 =18 *2+0