رازها

رازها

تمرین یادگیری

مقدمه

دستکاری بیت

هر بیت از یک عدد صحیح می‌تواند برای ذخیره‌ی یک مقدار دودویی استفاده شود. از آنجا که بسیاری از موقعیت‌ها اطلاعات دودویی دارند، مانند «درست» یا «غلط»، شامل بودن یا نبودن، روشن یا خاموش، نمایش دودویی یک عدد صحیح N بیتی روشی فشرده برای رمزگذاری وضعیت دودویی N مورد فراهم می‌کند. به همین دلیل، توانایی دستکاری بیت‌ها و بایت‌ها در اسمبلی ضروری است. مجموعه‌دستورات x86-64 انواع گسترده‌ای از دستورهای دستکاری بیتی ارائه می‌دهد.

دستکاری بیت تکی

این دستورها روی بیت‌های تکی در یک عملوند کار می‌کنند.

همه‌ی آن‌ها دو عملوند می‌گیرند؛ عملوند دوم اندیس بیتی را مشخص می‌کند که در عملوند اول روی آن عمل می‌شود. همه‌ی آن‌ها بیت انتخاب‌شده را در پرچم نقلی (CF) کپی می‌کنند.

اسم توضیح
bt بیت را بدون تغییر دادن هیچ عملوندی در CF کپی می‌کند
bts بیت را در CF کپی می‌کند و آن را در عملوند مقصد تنظیم می‌کند
btr بیت را در CF کپی می‌کند و آن را در عملوند مقصد صفر می‌کند
btc بیت را در CF کپی می‌کند و آن را در عملوند مقصد مکمل (معکوس) می‌کند

عملیات بیتی

عملیات بیتی روی همه‌ی بیت‌های یک عملوند انجام می‌شوند.

هر کدام از آن‌ها دستوری دارند که اسمش با عملیات بیتی انجام‌شده یکی است:

اسم توضیح
and ۱ اگر هر دو بیت ۱ باشند
or ۱ اگر حداقل یکی از بیت‌ها ۱ باشد
xor ۱ اگر بیت‌ها متفاوت باشند
not اگر بیت ۰ بود ۱؛ اگر بیت ۱ بود ۰

بیشتر آن‌ها دو عملوند می‌گیرند، روی هر دو یک عملیات بیتی انجام می‌دهند و نتیجه را در عملوند مقصد ذخیره می‌کنند. استثنا not است که فقط یک عملوند مقصد می‌گیرد.

ماسک

وقتی یک و صفر را به‌ترتیب به معنای شامل بودن و نبودن بگیریم، به یک عدد صحیح ماسک بیتی (یا به‌سادگی ماسک) می‌گوییم.

یک ماسک بیتی، موارد را «ماسک می‌کند»؛ چون صفر بودن بیت iاُم، مورد iاُم را کنار می‌گذارد و یک بودن آن، آن را نگه می‌دارد. همچنین معمولاً از یک ماسک بیتی استفاده می‌کنیم تا بعضی از بیت‌های یک عدد صحیح را نگه داریم و بقیه را کنار بگذاریم.

برای مثال، فرض کنید A عدد صحیحی باشد که نمایش دودویی آن چنین است:

اندیس ۷ ۶ ۵ ۴ ۳ ۲ ۱ ۰
بیت ۱ ۰ ۰ ۱ ۰ ۱ ۰ ۱

همچنین فرض کنید M عدد صحیحی باشد که نمایش دودویی آن چنین است:

اندیس ۷ ۶ ۵ ۴ ۳ ۲ ۱ ۰
بیت ۰ ۰ ۰ ۰ ۱ ۱ ۰ ۱

هر دو عدد صحیح 8 بیتی هستند. در این حالت می‌توان گفت M بیت‌های 0، 2 و 3 از A را انتخاب می‌کند و بقیه را کنار می‌گذارد.

دستورهای بیتی که پیش‌تر بحث شدند، برای دستکاری اعداد صحیح با ماسک مفید هستند. برای مثال:

  • برای صفر کردن بیت‌های A که با M انتخاب نشده‌اند، عملیات AND بیتی را انجام دهید: A AND M.
  • برای تنظیم کردن بیت‌های A که با M انتخاب شده‌اند، عملیات OR بیتی را انجام دهید: A OR M.

دستور TEST

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

اگر A عملوند اول و B عملوند دوم باشد:

پرچم تنظیم می‌شود وقتی
CF همیشه صفر می‌شود
ZF A AND B == 0
SF بیت علامتِ A AND B تنظیم شده است
OF همیشه صفر می‌شود

این دستور دو عملوند می‌گیرد و پرچم‌ها را به‌روزرسانی می‌کند، اما عملوندهای خود را تغییر نمی‌دهد.

عملیات شیفت

این دستورها بیت‌های عملوند مقصد را به اندازه‌ی تعداد موقعیت‌هایی که عملوند دوم مشخص می‌کند، شیفت می‌دهند. عملوند دوم باید یک عدد ثابت (یک immediate) یا ثبات cl (پایین‌ترین 8 بیت rcx) باشد.

اسم توضیح
shl/sal بیت‌ها را به چپ شیفت می‌دهد
shr/sar بیت‌ها را به راست شیفت می‌دهد

توجه کنید که مقدار شمارش در عملوند دوم به 5 بیت ماسک می‌شود، یا با یک عملوند مقصد 64 بیتی به 6 بیت. هر بیتی پس از آن عملاً نادیده گرفته می‌شود. این یعنی بیشترین مقدار شیفت 31 است، یا با یک عملوند 64 بیتی 63.

Shl / Sal

shl و sal هر دو دقیقاً یک عملیات یکسان را انجام می‌دهند؛ در واقع همان یک دستورند و فقط اسمشان فرق دارد.

هر بار شیفت به چپ انجام می‌شود، بیت‌هایی که به انتهای دنباله نزدیک‌تر از طول شیفت هستند، ابتدا به CF منتقل و سپس دور ریخته می‌شوند. در عوض، تعدادی بیت صفرشده‌ی جدید برابر با طول شیفت به ابتدا اضافه می‌شود.

از آنجا که هر بیت در یک عدد صحیح نماینده‌ی توانی از 2 است، شیفت به چپ به اندازه‌ی n موقعیت، اثر ضرب عدد صحیح در 2ⁿ را دارد.

Shr / Sar

دو دستور برای شیفت بیت‌ها به راست وجود دارد: shr و sar.

هر بار که یکی از این دو دستور استفاده شود، بیت‌هایی که به ابتدای دنباله نزدیک‌تر از طول شیفت هستند، ابتدا به CF منتقل و سپس دور ریخته می‌شوند. در عوض، تعدادی بیت جدید برابر با طول شیفت به انتها اضافه می‌شود.

تفاوت آنها این است که shr بیت‌های 0 را به انتهای چپ می‌برد، در حالی که sar اگر پرارزش‌ترین بیت تنظیم شده باشد 1 و در غیر این صورت 0 را می‌برد. این یعنی sar هنگام شیفت یک عدد صحیح علامت‌دار، علامت را حفظ می‌کند.

از آنجا که هر بیت در یک عدد صحیح نماینده‌ی توانی از 2 است، شیفت به راست به اندازه‌ی n موقعیت با shr اثر یک تقسیم بدون علامت بر 2ⁿ را دارد.

به همین ترتیب، شیفت به راست به اندازه‌ی n موقعیت با sar اثر یک تقسیم علامت‌دار بر 2ⁿ را دارد.

عملیات چرخش

این دستورها بیت‌های عملوند مقصد را به اندازه‌ی تعداد موقعیت‌هایی که عملوند دوم مشخص می‌کند، می‌چرخانند. عملوند دوم باید یک عدد ثابت (یک immediate) یا ثبات cl (پایین‌ترین 8 بیت rcx) باشد.

تفاوت چرخش و شیفت در این است که چرخش هیچ بیتی را دور نمی‌ریزد یا اضافه نمی‌کند. بیت‌هایی که با شیفت دور ریخته می‌شوند، در عوض به انتهای مخالف منتقل می‌شوند. بنابراین همه‌ی بیت‌ها باقی می‌مانند؛ فقط جایشان عوض می‌شود.

اسم توضیح
rol بیت‌ها را به چپ می‌چرخاند
ror بیت‌ها را به راست می‌چرخاند

توجه کنید که مقدار شمارش در عملوند دوم به 5 بیت ماسک می‌شود، یا با یک عملوند مقصد 64 بیتی به 6 بیت. هر بیتی پس از آن عملاً نادیده گرفته می‌شود. این یعنی بیشترین مقدار چرخش 31 است، یا با یک عملوند 64 بیتی 63.

سایر دستورهای دستکاری بیت

دستورهای مفید دیگری هم برای دستکاری بیت وجود دارد:

اسم توضیح
popcnt تعداد بیت‌های تنظیم‌شده را می‌شمارد
bsr اندیس پرارزش‌ترین بیت تنظیم‌شده را می‌گیرد. اگر هیچ بیتی تنظیم نشده باشد، نتیجه تعریف‌نشده است
bsf اندیس کم‌ارزش‌ترین بیت تنظیم‌شده را می‌گیرد. اگر هیچ بیتی تنظیم نشده باشد، نتیجه تعریف‌نشده است

این دستورها همه با دو عملوند 16 بیتی، 32 بیتی یا 64 بیتی کار می‌کنند. نمی‌توان از آنها با عملوندهای 8 بیتی استفاده کرد.

دستورالعمل‌ها

دوستتان همین حالا پیامی با یک راز مهم برایتان فرستاده است. چون نمی‌خواسته خواندنش برای دیگران آسان باشد، پیام با انجام یک سری دستکاری بیتی رمزنگاری شده است. باید متدهایی بنویسید که به رمزگشایی پیام کمک کنند.

Note

این‌ها دستورهای تک‌بیتی هستند که در این مفهوم به آن‌ها اشاره شده است:

نام توضیح
bt بیت را بدون تغییر دادن هیچ عملوندی در CF کپی می‌کند
bts بیت را در CF کپی می‌کند و آن را در عملوند مقصد تنظیم می‌کند
btr بیت را در CF کپی می‌کند و آن را در عملوند مقصد پاک می‌کند
btc بیت را در CF کپی می‌کند و آن را در عملوند مقصد مکمل (معکوس) می‌کند

این‌ها دستورهای بیتی هستند که در این مفهوم به آن‌ها اشاره شده است:

نام توضیح
and اگر هر دو بیت ۱ باشند، ۱
or اگر حداقل یکی از بیت‌ها ۱ باشد، ۱
xor اگر بیت‌ها متفاوت باشند، ۱
not اگر بیت ۰ بود ۱؛ اگر بیت ۱ بود ۰

این‌ها دستورهای شیفت هستند که در این مفهوم به آن‌ها اشاره شده است:

نام توضیح
shl/sal بیت‌ها را به چپ شیفت می‌دهد
shr/sar بیت‌ها را به راست شیفت می‌دهد

این‌ها دستورهای چرخش هستند که در این مفهوم به آن‌ها اشاره شده است:

نام توضیح
rol بیت‌ها را به چپ می‌چرخاند
ror بیت‌ها را به راست می‌چرخاند

این‌ها دستورهای متفرقه هستند که در این مفهوم به آن‌ها اشاره شده است:

نام توضیح
popcnt تعداد بیت‌های تنظیم‌شده را می‌شمارد
bsr اندیس پرارزش‌ترین بیت تنظیم‌شده را به دست می‌آورد. اگر هیچ بیتی تنظیم نشده باشد، نتیجه تعریف‌نشده است
bsf اندیس کم‌ارزش‌ترین بیت تنظیم‌شده را به دست می‌آورد. اگر هیچ بیتی تنظیم نشده باشد، نتیجه تعریف‌نشده است

1. استخراج ماسک

پیام در یک عدد صحیح ۱۶ بیتی رمزنگاری شده است. اما از این ۱۶ بیت، ۸ بیت بالایی در واقع بخشی از پیام نیستند، بلکه ماسکی هستند که باید در رمزگشایی استفاده شود.

تابع extract_higher_bits را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد و ۸ بیت بالایی آن را برمی‌گرداند.

extract_higher_bits(0b1010010011000101)
// => 0b10100100

2. استخراج پیام

توانایی استخراج ماسک کافی نیست؛ باید پیام را هم جدا کنید.

تابع extract_lower_bits را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد و ۸ بیت پایینی آن را برمی‌گرداند.

extract_lower_bits(0b1010010011000101);
// => 0b11000101

3. استخراج بیت‌های زائد

برخی بیت‌ها هم در پیام و هم در ماسک تنظیم شده‌اند. این اطلاعات بسیار مهمی است که بعداً استفاده خواهد شد.

تابع extract_redundant_bits را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد که هم پیام و هم ماسک را رمزنگاری کرده است، و یک عدد صحیح ۸ بیتی برمی‌گرداند که فقط بیت‌های زائد در آن تنظیم شده‌اند. بیتی در عدد برگردانده‌شده که هم در پیام و هم در ماسک ۱ است، باید ۱ تنظیم شود. همه‌ی بیت‌های دیگر باید پاک شوند.

extract_redundant_bits(0b1010010011000101);
// => 0b10000100

4. تنظیم همه‌ی بیت‌های پیام

در مرحله‌ی بعد، طبق ماسک، برخی بیت‌ها باید در پیام روی 1 تنظیم شوند.

تابع set_message_bits را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد که هم پیام و هم ماسک را رمزنگاری کرده است، و نتیجه‌ی تنظیم بیت‌های پیام روی ۱ را برمی‌گرداند. هر بیتی از پیام که بیت متناظرش در ماسک ۱ باشد، باید ۱ تنظیم شود. همه‌ی بیت‌های دیگر باید بدون تغییر بمانند، یعنی اگر از قبل تنظیم بودند تنظیم بمانند و اگر از قبل پاک بودند پاک بمانند.

set_message_bits(0b1010010011000101);
// => 0b11100101

5. چرخاندن کلید خصوصی

یک تکه از این معما در پیام صریحاً نیامده است: عدد ۱۶ بیتی 0b1011001100111100. این عدد کلید خصوصی مشترک شماست و باید از آن برای کمک به رمزگشایی پیام استفاده کنید.

برای این کار، ابتدا باید بیت‌های کلید خصوصی‌تان را به اندازه‌ی تعداد مشخصی موقعیت به چپ بچرخانید. تعداد موقعیت‌ها برابر است با تعداد بیت‌های زائدی که هم در پیام و هم در ماسک تنظیم شده‌اند.

تابع rotate_private_key را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد که هم پیام و هم ماسک را رمزنگاری کرده است، و نتیجه‌ی چرخاندن کلید خصوصی‌تان را برمی‌گرداند. این نتیجه یک عدد صحیح ۱۶ بیتی است.

rotate_private_key(0b1010010011000101);
// => 0b1100110011110010
Note

NASM (نتواید اسمبلر، همان اسمبلری که این ترک از آن استفاده می‌کند) از ثابت‌هایی با قالب دودویی که پیشوند 0b دارند پشتیبانی می‌کند. همچنین برای خوانایی بیشتر، استفاده از زیرخط (_) به عنوان جداکننده در یک ثابت را پشتیبانی می‌کند:

PRIVATE_KEY equ 0b1011_0011_0011_1100

6. قالب‌بندی کلید خصوصی

برای اینکه در رمزگشایی استفاده شود، کلید خصوصی‌تان باید قالب‌بندی شود تا بیت‌های مرتبط جدا شوند.

برای قالب‌بندی کامل یک کلید خصوصی، باید:

  • آن را بچرخانید.
  • پایین‌ترین بخش ۸ بیتی کلید خصوصی چرخیده را جدا کنید، که مقدار پایه است.
  • بالاترین بخش ۸ بیتی کلید خصوصی چرخیده را جدا کنید، که ماسکی است که باید روی مقدار پایه اعمال شود.
  • بیت‌هایی را در مقدار پایه که در ماسک هم تنظیم شده‌اند وارونه کنید.
  • همه‌ی بیت‌های نتیجه را وارونه کنید.

بیت وارونه‌شده اگر ۰ بود ۱ است و اگر ۱ بود ۰.

تابع format_private_key را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد که هم پیام و هم ماسک را رمزنگاری کرده است، و یک کلید خصوصی ۸ بیتی کاملاً قالب‌بندی‌شده برمی‌گرداند.

format_private_key(0b1010010011000101);
// => 0b11000001

7. پایان رمزگشایی

وقتی پیامی که همه‌ی بیت‌های مرتبطش تنظیم شده و کلید خصوصی قالب‌بندی‌شده را داشتید، وقت آن است که آن دو را کنار هم بگذارید تا پیام نهایی به دست آید.

پیام نهایی یک عدد صحیح ۱۶ بیتی است که:

  • ۸ بیت بالایی آن با کلید خصوصی قالب‌بندی‌شده پر می‌شود.
  • ۸ بیت پایینی آن با پیام، پس از تنظیم همه‌ی بیت‌های مرتبط، پر می‌شود.

تابع decrypt_message را پیاده‌سازی کنید که یک عدد صحیح ۱۶ بیتی می‌گیرد که هم پیام و هم ماسک را رمزنگاری کرده است، و یک عدد صحیح ۱۶ بیتی با پیام کاملاً رمزگشایی‌شده برمی‌گرداند.

این تابع باید از کلید خصوصی قالب‌بندی‌شده‌ای که با format_private_key تولید می‌کنید و همچنین از پیامی که همه‌ی بیت‌های مرتبطش با set_message_bits تنظیم شده استفاده کند.

decrypt_message(0b1010010011000101);
// => 0b1100000111100101
ویرایش از طریق GitHub این لینک در پنجره یا زبانه‌ی جدیدی باز می‌شود
x86-64 Assembly Exercism

آماده‌اید رازها را شروع کنید؟

در Exercism ثبت‌نام کنید تا x86-64 Assembly را همراه با 22 مفهوم130 تمرین و مربی‌گری انسانی واقعی یاد بگیرید و در آن استاد شوید، همه‌ی این‌ها رایگان.