تابع هش SHA-256؛ تحلیل خط به خط الگوریتم

در دنیای واقعی از اثر انگشت هر فرد برای تعیین هویت استفاده می‌شود چرا که اثر انگشت هر فردی منحصربه‌فرد است. در دنیای دیجیتال هم نیاز مشابه‌ای وجود داشت برای همین توابع هش رمزنگاری به وجود آمدند. این توابع هر نوع داده ورودی دیجیتالی (متن، عکس، نرم‌افزار و ...) را در یک فرآیند پیچیده محاسباتی و ریاضیاتی به یک خروجی منحصربه‌فرد تبدیل می‌کنند. این خروجی را هش، اثر انگشت دیجیتال یا امضای دیجیتال می‌نامند. توابع هش یک‌طرفه عمل می‌کنند؛ یعنی به‌گونه‌ای طراحی شده‌اند که نمی‌توان از خروجی یا همان هش به داده ورودی اصلی رسید. توابع هش رمزنگاری استانداردهای متنوعی دارد که خانواده SHA-2 یکی از مهم‌ترین آن‌ها است. استاندارد SHA-2 مجموعه‌ای از توابع هش رمزنگاری مشابه است که تابع SHA-256 از همه محبوب‌تر و پرکاربردتر است. از جمله مهم‌ترین کاربردهای آن می‌توان به استفاده در بلاک‌چینِ بیت‌کوین، ساخت امضای دیجیتال در گواهینامه‌های SSL و هش کردن گذرواژه در سیستم‌عامل‌های لینوکس و یونیکس اشاره کرد. در این مقاله قصد داریم، علاوه بر آشنایی کلی، با تحلیل الگوریتم‌ SHA-256، به درک کامل و عمیقی از روش رمزنگاری این تابع هش برسیم.

تابع هش SHA-256

تابع هش SHA-256 هر نوع داده ورودی را به یک خروجی عددی با طول ثابت 256 بیت (32 بایت) هش می‌کند. احتمال تصادم، به وجود آمدن هش یکسان برای دو ورودی غیریکسان، تقریباً صفر است. زیرا که خروجی «2 به توان 256» حالت را می‌تواند داشته باشد که تقریباً معادل تعداد اتم‌های جهان هستی است که دانشمندان بین «10 به توان 79» تا «10 به توان 82» تخمین زده‌‌اند. این تابع برای ورودی‌های مشابه دو هش کاملاً متفاوت تولید می‌کند به‌طوری‌که نمی‌توان به الگوی قابل‌تشخیصی پی ‌برد. در کنار امنیت بالا، ویژگی مهم دیگر این تابع سرعت هش کردن آن است که ورودی را در کسری از ثانیه هش می‌کند. همه این موارد در کنار هم باعث شده که این تابع بسیار کاربردی باشد. برای استفاده آنلاین از تابع هش SHA-256 می‌توانید از این لینک استفاده کنید. در ادامه چند نمونه هش را می‌بینیم:

تابع هش SHA-256 چگونه کار می‌کند؟

برای اینکه ساده‌تر بفهمیم که تابع هش SHA-256 چگونه کار می‌کند و چه مراحلی را برای رسیدن به هش از سر می‌گذراند می‌خواهیم همراه با توضیحات، یک مثال را هم جلو ببریم تا ملموس تر بفهمیم چه اتفاقاتی در هر مرحله الگوریتم بر روی داده ورودی می‌افتد. در این مثال می‌خواهیم از عبارت متنی "!Hello World" استفاده کنیم تا در نهایت به هش زیر برسیم:

7F83B1657FF1FC53B92DC18148A1D65DFC2D4B1FA3D677284ADDD200126D9069

تبدیل به باینری

اولین اتفاقی که پس از ورود داده به تابع هش می‌افتد تبدیل آن به فرمت باینری است. برای تبدیل حروف، اعداد و علائم به فرمت باینری باید از کد اسکی استفاده کنیم. مثلاً حرف «H» دارای کد اسکی 01001000 است یا «خط‌فاصله» کد اسکی 00100000 را دارد. در این لینک می‌توانید جدول کامل کد اسکی را ببنید.

ورودی "!Hello World" پس از تبدیل به فرمت باینری می‌شود:

"Hello World!" -> 01001000 01100101 01101100 01101100 01101111 00100000 01010111 01101111 01110010 01101100 01100100 00100001

پیش‌پردازش

اکنون که داده ورودی به فرمت باینری درآمده، قدم بعدی استاندارد کردن آن برای پردازش توسط الگوریتم است. به این کار پیش‌پردازش می‌گویند. مهم‌ترین مرحله پیش‌پردازش «پَدینگ پیام» است.

پَدینگ پیام:

هر داده ورودی باید قبل از محاسبه هش پَد شود؛ یعنی می‌بایست یک سری داده‌های اضافی به داده ورودی اصلی اضافه شود تا به یک اندازه‌ی ثابت برسد. در الگوریتم SHA-256 داده ورودی باید ضریبی از 512 بیت باشد زیرا که الگوریتم داده‌ها را در بلوک‌های 512 بیتی (64 بایتی) پردازش می‌کند.

در مثال "!Hello World"، داده ورودی 96 بیت دارد که کمتر از 512 بیت است. پس نیاز داریم آن را پَد کنیم. اگر داده ورودی ما بزرگ‌تر از 512 بیت می‌بود، می‌بایست آن را به بلوک‌های 512 بیتی تقسیم می‌کردیم.

اکنون می‌بایست 416 بیت دیگر به داده باینری "!Hello World" اضافه کنیم تا به یک بلوک کامل 512 بیتی تبدیل شود. الگوریتم SHA-256 برای این کار از روش زیر استفاده می‌کند:

• بعد از داده ورودی باینری شده، عدد «1» را اضافه می‌کنیم.
• سپس، به تعدادی عدد «0» (بعد از عدد «1») اضافه می‌کنیم تا 448 بیت از بلوک پر شود.

• در انتها، 64 بیت باقی‌ می‌ماند تا بلوک کامل (512 بیت) شود. در این 64 بیت می‌بایست مقدار طول داده‌ ورودی را قرار دهیم. در مثال ما، همان‌طور که قبلاً دیدیم طول داده ورودی 96 بیت است که عدد 96 به فرمت باینری 01100000 است. طول ورودی را در انتهایی‌ترین قسمت بلوک قرار می‌دهیم و قبل از آنقدر صفر اضافه می‌کنیم تا 64 بیت کامل شود.

الگوریتم اصلی SHA-256

در تصویر زیر، نمودار گرافیکی الگوریتم SHA-256 را مشاهده می‌کنید:

اگر قبلاً با الگوریتم‌های مشابه کار نکرده باشید، به نظر پیچیده و غیر قابل فهم می‌رسد. اما قصد داریم با تشریح آن و توضیح جزئیات به فهم آسان‌تری از ساختار این الگوریتم برسیم.

ورودی پیام (M)

اگر به سمت چپ بالای نمودار نگاه کنید، ورودی پیام، The message input (M)، را خواهید دید. ورودی پیام در مثال ما، بلوک 512 بیتی "!Hello World" است که در زیر می‌بینید. ما نیاز داریم برای پردازش، داده ورودی آن را به آرایه‌ 16 خانه‌ای از کلمات 32 بیتی تبدیل کنیم و از W0 تا W15 آن را برچسب بزنیم.

تبدیل به هگزادسیمال

این مسئله گفتن ندارد که هگزادسیمال، دستگاه اعداد پایه ۱۶، به طور گسترده توسط طراحان و برنامه‌نویسان کامپیوتری استفاده می‌شود. هر رقم هگزادسیمال، نشان‌دهندهٔ چهار بیت باینری است. این سیستم از ۰ تا ۹ برای مقادیر صفر تا نه و از حروف A, B, C, D, E, F برای مقادیر ده تا پانزده استفاده می‌کند. از طرفی، همان‌طور که قبلاً دیدیم، هش خروجی SHA-256 به فرمت هگزادسیمال است. برای همین از اینجا به بعد برای ساده‌تر شدن، فرمت باینری "!Hello World" را تبدیل به هگزادسیمال می‌کنیم.

• W0 = 48656C6C
• W1 = 6F20576F
• W2 = 726C6421
• W3 = 80000000
• W4 تا W14 = 00000000
• W15 = 00000060

ساخت Message Schedule

اگر به تصویر زیر دقت کنید، متوجه می‌شوید که یکی از ورودی‎‌ها به Round 63 کلمه W63 است. این در حالی است که ما فقط، تا الان، مقادیر W0 تا W15 را داریم. پس نتیجه می‌گیرم نیاز به 48 کلمه‌ی «W» دیگر هم داریم تا آرایه 64 خانه‌ای «W» کامل شود. در ادامه درباره الگوریتمی صحبت خواهیم کرد که مقادیر W16 تا W63 را محاسبه می‌کند.

تمامی کلمات W16 تا W63 در کادر Message Schedule، نمودار بالا، محاسبه می‌شود. برای محاسبه از معادله زیر استفاده می‌شود:

خُب، بیایم کمی این معادله ریاضی را بشکافیم تا آسان‌تر شود.

در این معادله، حرف t اشاره به عدد Round می‌کند. اگر ما در Round اول هستیم، که از دید برنامه‌نویسی یعنی Round 0، مقدار t عدد 0 است. بنابراین اگر W0 را دیدید، به این معنی است که این مقدار برای W در Round 0 است.

معادله σ1(x)

نماد ریاضیاتی که کمی مبهم در معادله به نظر مــی‌رسد σ1(x) است. این نماد معروف به سیگما1 است. معادله آن با این تابع محاسبه می‌شود.

قبل از اینکه بفهمیم که Message Schedule چگونه کار می‌کند نیاز داریم ابتدا با روش محاسبه σ1(x) آشنا شویم.

عملیات‌ جابجایی (Shift operations):

عملیات «RTOR» در معادله σ1(x) دو بار استفاده شده است. RTOR که با عنوان جابجایی چرخشی به راست (circular right-shift) شناخته می‌شود، مقدار ورودی را به اندازه ‌ای که در خود نماد مشخص شده به سمت راست، به شکل چرخشی، جابجا می‌کند. به عنوان نمونه، در عملیات ROTR17(x) می‌بایست مقدار X را به اندازه 17 بیت به سمت راست به شکل چرخشی جابجا کنیم. مثلا مقدار 10001001 را اگر به این عملیات بدهیم خروجی آن 11000100 می‌شود. برای دیدن جزئیات روی این لینک کلیک کنید.

عملیات بعدی در معادله «SHR» است که با نام جابجایی منطقی به چپ (logical left-shift) شناخته می‌شود. در عملیات «SHR10(x)» مقدار X به اندازه 10 بیت به سمت چپ جابجا می‌شود. برخلاف عملیات جابجایی چرخشی، در این عملیات داده در هر حرکت به سمت چپ از بین می‌رود. مثلاً اگر مقدار X را 10010010 در نظر بگیریم و در عملیات «SHR10(x)» قرار دهیم به مقدار 00000000 می‌رسیم. برای دیدن جزییات می‌توانید روی این لینک کلیک کنید.

عملیات XOR:

سومین و آخرین عملیاتی که احتیاج به توضیح دارد XOR است. XOR یک عملگر منطقی است که با سمبل ⊕ شناخته می‌شود. این عملگر به گونه‌ای عمل می‌کند که اگر هر دو ورودی «0» یا «1» باشد، خروجی «0» است. در غیر این صورت خروجی «1» خواهد بود. از آنجایی که این مبحث مرتبط با جبر بولی است و توضیحاتش فراتر از این مقاله است برای اطلاعات بیشتر می‌توانید از این لینک استفاده کنید.

محاسبه معادله Message Schedule:

تا اینجا برخی از جزییات مربوط به معادله را بررسی کردیم. یک نگاه دیگری به معادله اصلی بیندازیم:

از آنجایکه مقدار W0 تا W15 مشخص است می‎‌خواهیم مقادیر W16 تا W63 را از طریق معادلات بالا بدست آوریم. به عنوان نمونه، در مثال "!Hello World" می‌خواهیم مقدار W16 را محاسبه کنیم. پس معادله را بدین‌گونه می‌نویسیم:

از قبل داریم که:

• W0 = 48656C6C OR 01001000 01100101 01101100 01101100
• W1 = 6F20576F OR 01001000 01100101 01101100 01101100
• W9 = 00000000 OR 00000000 00000000 00000000 00000000
• W14 = 00000000 OR 00000000 00000000 00000000 00000000

خب، ابتدا بیایم مقدار σ1(W14) را محاسبه کنیم، محاسبات با فرمت هگزادسیمال انجام می‌شود:

σ1(W14) = ROTR17(W14) ⊕ ROTR19(W14) ⊕ SHR10(W14)

σ1(00000000) = ROTR17(00000000) ⊕ ROTR19(00000000) ⊕ SHR10(00000000)

σ1(W14) = 00000000

در قدم بعدی می‌بایست σ0(W1) را محاسبه کنیم که با معادله زیر بدست می‌آید:

σ0(x) = ROTR7(x) ⊕ ROTR18(x) ⊕ SHR3(x)

همان‌طور که می‌دانیم W1 برابر است با 48656C6C، پس داریم:

σ0(48656C6C) = ROTR7(48656C6C)⊕ROTR18(48656C6C)⊕SHR3(48656C6C)

σ0(48656C6C) = DEDE40AE ⊕ 15DBDBC8 ⊕ DE40AED

σ0(W1) = C6E1918B

جمع پیمانه‌ای:

ما الان مقادیر σ1 (W14) و σ0 (W1) را داریم و وقتش رسیده تا W16 را حساب کنیم:

W16 = σ1 (W14) + W9 + σ0 (W1) + W0

W16 = 00000000 + 00000000 + C6E1918B + 48656C6C

معادله بالا به نظر چند جمع ساده می‌رسد. اما نکته مهمی دارد. محاسبه جمعی که در معادله بالا است در اصل جمع پیمانه‌ای است نه جمع معمولی!

برای فهم بهتر جمع پیمانه‌ای، یک عدد 8-رقمی دسیمال (در مبانی 10) را فرض کنید. مثلاً اگر عدد 1 را با عدد 8-رقمی 99.999.999 جمع پیمانه‌ای کنیم، جواب مورد انتظار 100.000.000 نخواهد بود. بلکه جواب 0 است. چرا؟ قبلاً گفتیم عدد ما باید 8 رقمی باشد و نمی‌تواند 9 رقمی شود. مثل ساعت که عقربه‌ها بعد از 12 به 1 می‌رسد نه به 13! برای مطالعه بیشتر می‌توانید در این لینک به طور خلاصه با نظریه همنهشتی و حساب پیمانه‌ای آشنا شوید.

الان می‌توانیم محاسبه w16 را انجام دهیم. برای جمع از ماشین‌حساب آنلاین استفاده می‌کنیم.

W16 = 00000000 + 00000000 + C6E1918B + 48656C6C

جواب ماشین‌حساب می‌شود:

W16 = 10f46fdf7

اما از آنجایی که قرار بود جمع پیمانه‌ای باشد و از 8 رقم بیشتر نشود. نیاز داریم تا چپ‌ترین رقم را آن‌قدر حذف کنیم تا طول عدد به 8 رقم برسد. پس مقدار درست W16 برابر می‌شود با:

W16 = 0f46fdf7

برای مقداردهی W17 تا W63 به همین روشی که توضیح دادیم محاسبات را انجام می‌دهیم.

مقداردهی اولیه متغیرها:

تا الان بررسی کردیم که ورودی‌های W چگونه بدست می‌آید. دوباره برگردیم به نمودار:

اگر به نمودار بالا نگاه کنید، هشت متغییر a, b, c, d, e, f, g, h را می‌بینید که وارد هر Round شده‌ و از آن خارج می‌شوند. در ادامه متوجه خواهید شد که این هشت متغییر نقش کلیدی و مهمی را، در فرآیند ساخت هش توسط الگوریتم، ایفا می‌کنند. اما این هشت متغییر چیست و مقادیر اولیه آنها چگونه بدست می آید؟

در نمودار بالا، این هشت متغییر در (i-1)H نشان داده شده است که در شروع (0)H است. برای مقداردهی این هشت متغیر در (0)H داریم:

• H(0)a = 6a09e667
• H(0)b = bb67ae85
• H(0)c = 3c6ef372
• H(0)d = a54ff53a
• H(0)e = 510e527f
• H(0)f = 9b05688c
• H(0)g = 1f83d9ab
• H(0)h = 5be0cd19

اما این مقادیر از کجا می‌آید؟ در واقع این مقادیر در استاندارد الگوریتم SHA-256 به عنوان مقادیر اولیه تعریف شده‌اند و همیشه ثابت هستند. بر اساس استاندارد FIPS 180-4 این مقادیر از جذر 8 عدد اول بدست می‌آیند. به عنوان نمونه، برای بدست آوردن متغیر H(0)a داریم:

مقدار ثابت K

بعد از محاسبه W و مقدار دهی هشت متغیر a تا h، حالا نوبت به بررسی متغیر K می‌رسد. همان‌طور که در نمودار زیر می‌بینید، 64 متغیر 32 بیتی K داریم که هر کدام برای یک Round است.

بر اساس استاندارد FIPS 180-4 مقادیر K از ریشه سوم، 64 عدد اول بدست می‌آید. مقادیر K بدین ترتیب‌اند:

به عنوان نمونه، اولین متغیر،k0، به این روش محاسبه می‌شود:

محاسبه هش SHA-256

تا اینجا تمامی ورودی‌های Round را بررسی کردیم. اما خود Round چیست؟ Round درواقع محاسبه هش SHA-256 است. یا به زبانی دیگر، یک انتزاع از مجموعه‌ معادلات ریاضیاتی است که خروجی آن هشت متغیر بروزرشده‌ی a, b, c, d, e, f, g, h است. در نهایت پس از انجام 64 بار Round، به یک قدمی هش خروجی خواهیم رسید.

در تصویر زیر الگوریتم داخلی Round را می‌بینید:

اگر بخواهیم الگوریتم بالا را به زبان ریاضی بنویسیم، می‌شود:

در الگوریتم بالا، مهم‌ترین معادلاتی که نیاز داریم محاسبه کنیم T1و T2 است. مقادیر ورودی‌های W، هشت متغیر a تا h و همچنین K را از قبل بدست آورده‌ایم. در معادلات T1 و T2 چند عملیات و نماد جدید ریاضیاتی می‌بینیم که قرار است در موردشان صحبت کنیم و مثال "!Hello World" را جلو ببریم.

عملیات (x)∑

دو سمبل (0)∑ و (1)∑ که در معادله T1 و T2 است از معادلات زیر بدست می‌آید.

در مورد ROTR و ⊕ قبلاً صحبت کرده‌ایم و روش محاسبات‌شان مشخص است.

عملیات Maj

تابع Maj (a,b,c) که در معادله T2 استفاده شده، از معادله زیر بدست می‌آید:

Maj (a,b,c) = (a ^ b) ⊕ (a ^ c) ⊕ (b ^ c)

در معادله Maj تنها عملگری که معرفی نکرده‌ایم And است که با سمبل «^» نمایش داده می‌شود. And، هم مانند XOR، یکی دیگر از عملگرها در جبر بولی است. And به زبان ساده یعنی اینکه اگر خروجی 1 باشد ورودی‌های هم حتماً 1 هستند. در جدول زیر تمامی حالت‌های این عملگر را می‌بینید.

تابع شرطی

تابع Ch(e, f, g) که در معادله T2 استفاده شده است از معادله زیر بدست می‌آید:

Ch(e, f, g) = (e ^ f) ⊕ (~ e ^ g)

تنهای عملگری که در این تابع معرفی نشده است، اپراتور Not است که با نماد «~» نمایش داده می‌شود. Not هم یکی دیگر از عملگرها در جبر بولی است. Not یعنی اینکه اگر ورودی 0 باشد خروجی 1 می‌شود و برعکس.

محاسبه هش "!Hello World"

قصد داریم که Round 0 را برای مثال "!Hello World" محاسبه کنیم. مقادیر زیر را داریم:

• W0= 48656C6C
• k0 = 428A2F98
• a = 6a09e667
• b = bb67ae85
• c = 3c6ef372
• d = a54ff53a
• e = 510e527f
• f = 9b05688c
• g = 1f83d9ab
• h = 5be0cd19

این مقادیر را در معادلات زیر جایگذاری می‌کنیم:

T1= 5be0cd19 +  ∑1(510e527f) + ch(510e527f, 9b05688c, 1f83d9ab) + 428A2F98 +48656C6C

T2 = ∑0(6a09e667) + Maj(6a09e667, bb67ae85, 3c6ef372)

پس از محاسبه معادله بالا، مقادیر T1 و T2 را بدست می آوریم و می توانیم با استفاده از آنها بقیه محسابات را به راحتی انجام دهیم تا مقادیر a تا h به‌روز شوند. به‌روزرسانی متغیرهای a تا h در هر Round اتفاق می افتد. الگوریتم Round را 63 بار دیگر انجام می‌دهیم تا در نهایت مقدار خروجی‌ متغیرهای a تا h می‌شود:

• a = 1579CAFE
• b = C48A4DCE
• c = 7CBECE0F
• d = A351E123
• e = AB1EF8A0
• f = 08D10E9C
• g = 2B59F855
• h = B68CC350

جمع نهایی:

به تصویر زیر نگاه کنید:

در این مرحله که آخرین مرحله الگوریتم SHA-256 است، می‌بایست هشت متغیر a تا h که از خروجی 63 Round بدست آمده را با متغیرهای a تا h که در ابتدا یعنی Round 0 داشتیم، جمع پیمانه‌ای کنیم. این عملیات ریاضی به ما مقادیر H0 تا H7 را می دهد که در نهایت با چسباندن آنها در کنار هم به هش تابع می‌رسیم.

در مثال “!Hello World” بعد از جای‌گذاری مقادیر اشاره شده و انجام محاسبات جمع، به مقادیر زیر برای H0 تا H7 می‌رسیم:

• H0 = 7F83B165
• H1 = 7FF1FC53
• H2 = B92DC181
• H3 = 48A1D65D
• H4 = FC2D4B1F
• H5 = A3D67728
• H6 = 4ADDD200
• H7 = 126D9069

با چسباندن مقادیر H0 تا H7 در کنار هم به هش تابع می رسیم که در مثال “!Hello World”، همان‌طور که انتظار هم داشتیم، می‌شود:

7F83B1657FF1FC53B92DC18148A1D65DFC2D4B1FA3D677284ADDD200126D9069