\documentclass{article} \usepackage{graphicx} \usepackage{subfig} \usepackage{array} \usepackage[left=1.5cm,right=1.5cm]{geometry} \usepackage{tikz} \usepackage{pstricks,pst-node,pst-tree} \usepackage{LectureTemplate} \usepackage{xepersian} \settextfont[Scale=1.1]{Yas} \setdigitfont{Yas} \begin{document} \handout {مبانی رمزنگاری} {1} {پاییز95} {سیستم های رمز متقارن} {علی مرادیان} \section{پیشنیاز ریاضی} \begin{definition} (الگوریتم تقسیم) به ازای اعداد صحیح $a$ و $b$ و به شرط $b>0$ اعداد صحیح و منحصر به فرد $q$ و $r$ وجود دارند به طوریکه : \[\begin{array}{cc} \begin{array}{l} a=qb+r\\ \end{array}&\begin{array}{r} 0\leq r < b\\ \end{array} \end{array}\] \end{definition} \begin{example} \end{example} $$43=(1\times26)+17 ,0\leq 17 < 26 $$ $$20=(0\times26)+20 ,0\leq 20 < 26 $$ \\ \\ \begin{definition} (همنهشتی) فرض کنید $n$ یک عدد صحیح مثبت باشد.آنگاه اعداد صحیح $a$ و $b$ را به پیمانه $n$ همنهشت گویند و آن را با رابطه $a \equiv b \pmod{\ n}$ نشان می دهند هرگاه : \\ $$n \mid a -b \Longleftrightarrow \exists k\in Z : nk=a-b$$ \end{definition} \begin{remark} فرض کنید $a \equiv b \pmod{\ n}$ باشد و باقیمانده تقسیم $a$ بر $n$ برابر $r$ باشد, آنگاه باقیمانده تقسیم $b$ بر $n$ نیز برابر $r$ است. \end{remark} \begin{example} برخی اوقات لازم است مقدار یک عدد را در پیمانه عددی چون 26 بدست آوریم.به محاسبات زیر توجه کنید : \\ \begin{align*} 43 &\equiv 17 \pmod{\ 26}\Longleftrightarrow 43=(1\times26)+17\\ 20 &\equiv 20 \pmod{\ 26}\Longleftrightarrow 20=(0\times26)+20\\ 26&\equiv 0 \pmod{\ 26}\Longleftrightarrow 26=(1\times26)+0\\ -43 &\equiv 9\pmod{\ 26}\Longleftrightarrow -43=(-2\times26)+9\\ -20&\equiv 6 \pmod{\ 26})\Longleftrightarrow -20=(-1\times26)+6\\ -26&\equiv 0 \pmod{\ 26}\Longleftrightarrow -26=(-1\times26)+0\\ \end{align*} \end{example} \begin{definition} (مجموعه $Z_{m}$ ) این مجموعه به صورت زیر تعریف می شود : $$Z_{m}= \{0 , 1 , ... , m-1 \}$$ \end{definition} \begin{example} $$Z_{26}= \{0 , 1 , ... , 25 \}$$ \end{example} \begin{definition} {\itshape (معکوس پذیری یک عضو در $Z_{m}$ ) اگر $a\in Z_{m}$ معکوس پذیر باشد , آنگاه گوییم $a$ در $Z_{m}$ معکوس دارد اگر $a$ و $m$ نسبت به هم اول باشند. در این صورت معکوس $a$ را با $a^{-1}$ نشان می دهند.} \end{definition} \begin{remark} رابطه $a$ و $m$ و $a^{-1}$ به صورت زیر است : \\ $$aa^{-1} \equiv 1 \pmod{\ m}$$ $$m \mid aa^{-1} -1 \Longleftrightarrow \exists k\in Z : mk=aa^{-1}-1 $$ \end{remark} \begin{definition} تعداد اعضای معکوس پذیر در $Z_{m}$ : \\ فرض کنید $m$ به صورت زیر به حاصلضرب توان هایی از اعداد اول تجزیه شده باشد : $$m=p_{1}^{\alpha_{1}}.p_{2}^{\alpha_{2}}...p_{k}^{\alpha_{k}}$$ به طوری که $p_{i}$ ها همه اعداد اول و $\alpha_{i}$ ها عضو اعداد طبیعی هستند . \\ آنگاه تعداد اعضای معکوس پذیر مجموعه $Z_{m}$ را با تابع فی اویلر به صورت زیر می توان بدست آورد: \\ $$\varphi(m)=(1-1 / p_{1})(1-1 / p_{2})... (1-1 / p_{k})= m \prod_{i=1}^{k} (p_{i}-1 /p_{i} )$$ \end{definition} \begin{example} تعداد اعضای معکوس پذیر در $Z_{26}$ را بدست می آوریم. \\ $$26=13 \times 2 \Longrightarrow \varphi(26)=(1-1 / 13)(1-1 / 2)=12$$ \end{example} \begin{remark} اعضای معکوس پذیر در $Z_{26}$ عبارت است از مجموعه زیر : \\ $$\{1,3,5,7,9,11,15,17,19,21,23,25\}$$ \\ معکوس این اعداد را در زیر می آوریم : $$1^{-1}= 1 , 3^{-1}= 9 ,5^{-1}=21,7^{-1}= 15 , 11^{-1}= 19,17^{-1}= 23 $$ $$25^{-1}= 25 , 9^{-1}= 3 ,21^{-1}=5,15^{-1}= 7 , 19^{-1}= 11,23^{-1}= 17$$ \end{remark} \begin{theorem} ماتریس $A_{n\times n}$ را معکوس پذیر گویند اگر و فقط اگر : $$\exists A^{-1} : A.A^{-1} =A^{-1} .A= I_{n\times n}$$ \end{theorem} \begin{theorem} در $Z_{m}$ ماتریس $A$ معکوس پذیر است اگر و فقط اگر $m$ ,و دترمینان ماتریس $A$ نسبت به هم اول باشند. \end{theorem} \begin{definition} دترمینان ماتریس $A_{n\times n}$ که $A=[a_{ij}]$ برابر است با : $$det(A)=\sum_{j=1}^{n} (-1)^{i+j}a_{ij}det(A_{ij})$$ \\ که $A_{ij}$ ماتریسی است که از حذف سطر $i$ ام و ستون $j$ ام ماتریس $A$ بدست می آید. \end{definition} \begin{definition} اگر $A$ ماتریسی معکوس پذیر باشد داریم : \\ $$A^{-1}= (1/det (A))A^{*}$$ \\ که: \\ $$A^{*}=\begin{pmatrix} \overline{A_{11}} &\overline{A_{21}} &\overline{A_{31}} \\\overline{A_{12}} &\overline{A_{22}} &\overline{A_{32}} \\\overline{A_{13}} &\overline{A_{23}} &\overline{A_{33}} \end{pmatrix}$$ \\ و هر $\overline{A_{ij}}$ به صورت زیر بدست می آید: $$\overline{A_{ij}}=(-1)^{i+j}det(A_{ij})$$ \end{definition} \begin{definition} در حالت خاص فرمول معکوس ماتریس $A_{2\times 2}$ به صورت زیر است : \\ اگر $$A=\begin{pmatrix} a&b\\c&d \end{pmatrix}$$ \\ باشد داریم : \\ $$A^{-1}= (1/ad-bc)\begin{pmatrix} d&-b\\-c&a \end{pmatrix}$$ \end{definition} \begin{example} اگر $$A=\begin{pmatrix} 11&8\\3&7 \end{pmatrix}$$ \\ باشد داریم : \\ $$A^{-1}= (1/77-24)\begin{pmatrix} 7&-8\\-3&11 \end{pmatrix}=(1/53)\begin{pmatrix} 7&-8\\-3&11 \end{pmatrix}$$ \\ وبالاخره در پیمانه 26 داریم : \\ $$A^{-1}=\begin{pmatrix} 7&18\\23&11 \end{pmatrix}$$ \end{example} \begin{example} اگر $$A=\begin{pmatrix} 1&2&4\\3&1&1\\2&0&1 \end{pmatrix}$$ \\ بدست آوردن معکوس ماتریس ابتدا دترمینان آن را از روش ساروس بدست می آوریم : $$det(A)=-9$$ \\ حال باید با بدست آوردن $\overline{A_{ij}}$ ها ماتریس $A^{*}$ را بدست آوریم.برای نمونه ماتریس $\overline{A_{11}}$ را بدست می آوریم. \\ داریم : $${A_{11}}=\begin{pmatrix} 1&1\\0&1 \end{pmatrix}$$ \\ $$det(A)=1\Longrightarrow \overline{A_{11}} = -1^{2}\times1=1 $$ \\ به همین ترتیب بقیه $\overline{A_{ij}}$ ها را بدست می آوریم. داریم : $$A^{*}=\begin{pmatrix} 1&-2&-2\\-1&-7&11\\-2&4&-5 \end{pmatrix}$$ \\ در نتیجه : $$A^{-1}=(-3)\begin{pmatrix} 1&-2&-2\\-1&-7&11\\-2&4&-5 \end{pmatrix}=\begin{pmatrix} -3&6&6\\3&21&-33\\6&12&15 \end{pmatrix}$$ \\ که (3-) معکوس عدد 9 (دترمینان ماتریس) است. \\ درنهایت با بردن اعداد به پیمانه 26 داریم : $$A^{-1}=\begin{pmatrix} -3&6&6\\3&-5&-7\\6&14&-11 \end{pmatrix}$$ \end{example} \begin{definition} جایگشت : یک جایگشت روی مجموعه $A$ تابعی دو سویی مانند $f:A\longrightarrow A$ است. \end{definition} \begin{example} اگر $A = \{1,2,3,4,5,6\}$ در نتیجه $(1\rightarrow 2,2 \rightarrow 4 , 3\rightarrow 5 , 4 \rightarrow 6 , 5 \rightarrow 1 , 6 \rightarrow 3)$ یک جایگشت روی مجموعه $A$ خواهد بود. \end{example} \begin{theorem} اگر $|A|=n$ باشد آنگاه تعداد جایگشت های روی $A$ برابراست با $n!$ \end{theorem} \end{document}