پرس و جو روی داده های رمز شده

صفحه 1:
پرس و جو روی داده های رمز شده علی هادوی خرداد ۸۸ درس امنیت پایگاه داده 

صفحه 2:
مقدمه ۶ روش‌های کنترل دسترسی برای محافظت از داده ها کافی يسنن - سرقت رسانه محتوى داده - عدم اعتماد به اعمال كننده خط مشى هاى كنترل دسترسى - امكان دور زدن مكانيزم هاى كنترل دسترسى توسط مهاجمين pw 9 Database as A Service ow! ons 7 bo * ‏های کار گزار غیرقابل اعتماد‎ عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 3:
مدل پایگاه داه به عنوان خدمت * بايكاه داده به عنوان خدمت (5©15106 4 25 192188256) به عنوان رویکردی جدید در برون‌سپاری پایگاه داده‌ها * در دسترس بودن داده ها توسط کار گزار تضمین می شود. *_کلیه اعمال مدیریت داده را کا رگزار فراهم می کند. *_کارگزار از نظر نگهداری داده‌ها و عدم ارسال عمدی پاسخ اشتباه مورد اعتماد است. *_کا رگزار در مورد محرمانگی داده‌ها مورد اعتماد نیست. - کار گزار درستکار ولی کنجکاو است (کتامنتاه ‎(Honest but‏ لان اذك ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 4:
مدل پایگاه داده به عنوان خدمت * چالش اصلی در این مدل تأمین امنیت داده‌های برون‌سپاری شده است. ۶ راه حل اولیه رمزنگاری داده های برون‌سپاری شده است. * برای حفظ محرمانگی مالک داده, داده خود را رمز کرده و آن را در پایگاه داده رمز شده در سمت کار گزار ذخیره میی کند. * ریزدانگی رمزنگاری به خط مشی های محیط برای سطح دسترسی, امنیت و کارایی بستگی دارد. - بیشتر فعالیت ها ریزدانگی را در سطح چندتایی تعریف کرده اند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 5:
عناصر مدل 10845 مالک داده‌ها: فرد یا سازمان است که داده‌ها را ایجاد و آن را برون‌سپاری. می کند. کاربر: پرس‌وجوها را به سیستم ارانه م ی کند. کارخواه: پرس‌وجوهای کاربر را به پرس‌وجوهای قابل اجرا روی داده‌های رمزشده تبدیل می کند. کا رگزار: محل ذخیره‌ی داده‌های رمز شده است و پرس‌وجوهای ارسالی از سمت کارخواه را روی داده‌های رمزشده اجرا کرده و نتیجه را به کارخواه ارائه می‌دهد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 6:
سناريوى برس و جو در مدل 1045 كاربر برس و جوى © رابا توجه به اسكيماى بايكاه داده ی رمز نشده 8 از طريق كارخواه وارد می کند. ‎ -‏ برون سبارى داده مى تواند از ديد كاربر شفاف باشد. كارخواه برس و جوى كاربر را به دو بخش 09 و 00 تقسيم مى كند. 09 برس و جوى اعمال شده بو روی داده هاى رمز شده در سمت كارعزار و ©06 برس و جوى اعمال شده در سمت كارفرما بر روى ذاده هاى بركثتى از ار زره سار خواهاست: أ ارخواه ساغتار يايكاه ذاده عادى و رهز شده وا میداد کارگزار پرس و جوی 625 را روی داده رمز شده اجرا و نتایج (مجموعه ای از چندتایی های رمز شده) را به کارخواه بر میگرداند. کارخواه نتایج را رم زکشایی کرده و چندتایی های اضافی را با اعمال 006 به نتایج اولیه حذف می کند. نتايج نهابى به كارير ارائه مى شود. عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 7:
ij ۱ 0 سناریوی پرس و جو در مدل ‎DAS‏ | تم ‎a‏ ‏0 

صفحه 8:
ملاحظات رمزنگاری در برون سپاری داده روش هایی که بتوانند به طور مستقیم با داده های رمز شده کار کند باید ملاحظات زیر را درنظر بگیرند: - میزان اعتماد به کارگزار * در مدل 10۸5 امکان رمزگشایی توسط کارگزار تامطمتن وجود ندارد. - کارایی روش اجرای پرس و جو * رمزکنایی کل داده های قبل از اجرای پرس و جو کارا یست. - تم رکز اجرای اعمال در سمت کار گزار - سربار قابل قبول برای ذخیره سازی و ارتباطات بین کارفرما و کار گزار - ریزدانگی رمزنگاری * اگررمزتگاری بصورت درشت‌دانه باشد امكان بهيناسازى برس وجو كم مى شود * رمزتكارى به صورت ريز دانه نيز كارابى را كمتر و در شرايطى به ممکن است به مهاجم اجازه استتتاج از داده‌ها را يدهد. - کنترل دسترسی در سیستم های چند کاربره عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 9:
ملاحظات رمزنگاری در برون سپاری داده (۲) ۰ مقاومت در برابر حملات احمله متن رمزشده معلوم: به طور کلی فرض می‌شود که مهاجم به داده رمزشده دسترسی دارد. هدف در این حمله شکستن متن رمزشده خاص يا بيدا كردن كليد است. حمله متن اصلی معلوم: مهاجم به تعدادی متن اصلى و معادل رمزشده آن‌ها دسترسی دارد عه از آن برای به دست آوردن بقیه‌ی متون رمزشده یا پی بردن به کلید رمز استفاده م ی کند. حمله متن اصلی انتخابی: مهاجم می‌تواند معادل رمزشده متن اصلی دلخواه خود را به دست بیاورد. لین حمله, نوع قویتری نسبت به حمله‌ی متن اصلی معلوم است. حمله متن رمز شده انتخابی: مهاجم می‌تواند رمزگشایی شده معادل متن رمزشده دلخواه را بدست آورد. حملات تحلیل فرکانسی: معکن است مهاجم (50:۳05) اطلاعات اولی‌ای راجع به دامنه مقادیر و فرکانس رخداد داده‌های رمزنشده داشته باشد و از آن برای نفوذ به پایگاه داده استفاده کند. حملات مبتنی بر اندازه: ممکن است مهاجم اطلاعاتی راجع‌به ارتباط طول متن اصلی و متن رمزشده داشته باشد.بنابراین اگر مهاجم مجموعه‌ای از داده‌های اصلی و ستن رسز شده مصادل را داشته باشد می‌تواند بهپایگاه داده حمله کند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 10:
ملاحظات رمزنگاری در برون سپاری داده (۳) * پشتیبانی از انواع پرس و جو - پرس و جو روی داده های عددی * پرس و جو با شرط تساوی * پرس و جوی بازه ای - پرس و جو روی داده های رشته ای * پرس و جو با شرط تساوی * پرس و جو های تطبیق الگویی - پرس و جوهای شامل توابع تجمعی عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 11:
روش های جستجو روی داده های رمز شده * جستجوی مستقیم روی داده های رمز شده * جستجوی مبتنی بر شاخص * روش های مبتنی بر حفظ ترتیب روش های مبتنی بر توابع همربخت اختفایی عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 12:
جستجوی مستقیم روی داده های رمز شده * داده به گونه ای رمز می شود که جستجو بتواند دقیقاً روی همان داده رمز شده به صورت مستقیم صورت گیرد. * سانگک روشی را بر اساس این ایده برای جستجو روی داده های رشته ای ارائه داده است. ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 13:
روش 50170 - معرفی جستجوی کلمات روی اسناد رمز شده (تمر کز بر 1013 نیست) كار برد مفهوم دریچه کار گزار می‌تواند با گرفتن اطلاعات کوچکی در مورد هر کلمه (دریچه)؛ جستجو را بدون اطلاع از کلمات دیگر متن انجام دهد. توابع مبتنی بر دریچه توابعی هستند که محاسبه‌ی معکوس آنها بدون داشتن اطلاعات خاصی به نام دریچه مشکل است. در رمزنگاری مبتنی بر دریچه, رم زگشایی با داشتن دریچه امکان‌پذیر است. در این روش‌ها, به همراه هر کلمه‌ای که کارخواه جستجوی آنرا تقاضا کرده است. دریچه‌ی آن نیز ارسال می‌شود. بدین شکل کارگزار فقط می‌تواند کلمه درخواست شده را رمزکشایی عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 14:
روش ‎Song‏ - رم زگذاری متن اصلی به تعدادی ‎bw dol‏ طول یکسان ( «بیت) تقسیم می شود. اسناد اصلی پس از رمزشدن به روش شرح داده شده به سمت کا رگزار ارسال و در آنجا ذخیره می‌شوند. کار گزار با دریافت دریچه‌ای از طرف کارخواه می تواند کلمه‌ی مورد نظر کاربر را جستجو کند. پارامترهای رمزنگاری 1 : مولدلعداد شبه تسصادفی 2 ۲ 9]: تولبع‌شبه تصادفی 3 > كليد تلبع ؛ (سرلوتهام كلواتعتنئ لسك F:f , (first n-m bits of 15 )980(( ‏دریچه هر كلمه: كليد تابع‎ ۶ عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 15:
روش 50100 - رم زگذاری(۲) ‎٠»‏ رمزگذاری در دو سطح انجام می شود. - سطح اول: * هر کلمه با یکی از الگوریتم‌های رمزنگاری متقارن و کلید (16") رمز می شود. *_کارگزار در هنگام اجرای پرسوجو از کلمه‌ی درخواست شده کارخواه مطلع نمی شود. - سطح دوم: * مولد شبه تصادفیک . دنبالهای از اعداد شبه تصادفی ,5 با طول 10-190 بیت به تعداد کلمات متن اصلی ایجاد می کند. * اعداد شبه تصادفی تولید شده ,5ب استفاده از تابع "1 درهم‌سازی شده و خروجی " بیتی تولید می شود. ۰ (رمزشده‌ی لایه‌ی اول هر کلمه (19۸).برظ)) با ( ,5 و حاصل درهم‌سازی شده در مرحله ‎AJB‏ ‏0 می‌شود. * نتیجه‌ی لایه‌ی دوم رمزتگاري کلمه‌ی ,14 به عنوان امین کلمه‌ی متن رمزشده (:6) در سند. رمزشده قرار مى كيرد. ‎ ‏عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 16:
| 0 fe 8 | 3 He a] | | fe I if روش 5000- رم زگذاری(۳) 

صفحه 17:
روش ‎Song‏ - اعمال پرس و جو کارخواه برای جستجوی یک کلمه ( *) در اسناد رمزشده؛ معادل رمز شده‌ی لایه‌ی اول کلمه (360).) به همراه دريجدى آن ( (1:)34) را به کارگزار ارسال می‌کند. ۲ كارسزار با دريافت ((7.)18) كلمات تمام اسناد را با آن 26018 می‌کند. .2 اگر کلمه‌ی ام سندی با کلمه‌ی درخواست شده برابر باشد. حاصل (,1) 166013 باید ساختاری به شکل <(,5) ررم‌یم ,1۳ برگ > داشته باشد. برای بررسی وجود ساختار فوق برای کلمه‌ی مام متن رمزشده. حاصل تابع 1 روی ‎ow HIM‏ پرارزش ,1 به دست آورده می‌شود. ۶ ار مقدار به دست آمده با بیت باقی‌مانده‌ی .1 برابر باشد. ساختار برقرار بوده و کلمه‌ی ۴ام متن رمزشده به همراه سندی که به آن متعلق است در مجموعه‌ی جواب ارسالی به کارخواه قرار می گیرد. ۰ تابع "۶ یک تابع درهم‌ساز دارای برخورد است. بابراین امکان وجود اشتباه مثبت در نتایج ارسالی به کارخواه وجود دارد. ‎١‏ در سمت کارخواه يس از رمزكثايى سند مقدار اصلی کلمه‌ی پیدا شده با کلمه‌ی درخواست شده‌ی کاربر مقایسه می‌شود تا ناج درستی به کاربربرگردانده شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 18:
روش ‎٩0۳0‏ - رم ز گشایی برای رم زگشایی کلمه‌ی ام سند رمزشده (,6)» ابتدا 11-09 بیت پرارزش ,6 با » رک ۴ می‌شود و 72-70 بيت پر ارزش 5.619 به دست می آید. از مقدار فوق برای ساختن دریچه‌ی 147 استفاده می‌شود. اعمال دریچه بدست آمده و 10-۳0 بیت پر ارزش ,5به تابع «دء 7 بيت نتيجه دارد که با 08 کردن با «بیت کم ارزش 6,۰۳ بیت کم ارزش (18).رت حاصل می شود. بدي ترتیب تمام بیت‌های (5,.)۲۷ به دست میآیند. ‎E(w)‏ یم زکشایی‌شده تا مقدار اصلی ۲۶ حاصلشود. ‏1۸ عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 19:
ویژگی های روش 5070 کار گزار نمی تواند در مورد متن اصلی تنها با استفاده از متن رمز شده اطلاعاتی بدست آورد. سربار ذخیره سازی و ارتباطاتی آن کم است. نتیجه حاوی مکان هلیی از سند است که 1۷ در تن ظاهر شده است و ممکن است دارای اشتباهات مثبت باشد. اشتباهات مثبت جا مقدار ۰« مرتبط است. هر جواب اشتباه با احتمال "1/2 رخ می دهد. بنابراین برای سندی با طول 1 كلمه انتظار 1/2 جواب اشتباه وجود دارد. متن بايد تقسيم به كلماقى جا طول مساوى شود كه با توجه به ساختار زبان» روش مناسبى عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 20:
ویژگی های روش )2( ‎Song‏ امکان جستجو با هر طول دلخواه وجود ندارد. فقط می‌توان کلمات با طول 21 یا ضریبی از بیت را جستجو کرد. گروه محدودی از الگوها قابل جستجو است. - الگوهایی به شکل"[2]2-2" با تبدیل به 22 ر... رطق رططق ره قابل جستجو هستند؛ - جستجوی الگوهایی به شکل "#29" مشکل است. زیرا تعداد رشته‌های تولیدی سيار زياد خواهند شد. در الكوريتم سانگ. برای یافتن هر کلمه باید کل محتویات تمام اسناد جستجو شود. زمان جستجو نسبت به طول متن خطی است. بنابراین در قابل مقیاس بزر کك (مانند پایگاه داده) کارا نیست. - یک روش افزایش سرعت بکارگیری شاخص های از پیش تعریف شده است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 21:
جمع بندی - جستجوی مستقیم روی داده رمز شده فضای ذخیره سازی نسبت به ذخیره سازی داده اصلی تفاوت زیادی ندارد. معمولاً احتمال اجرای حملات فر کانسی نسبت به روش مبتنی بر شاخص کمتر است. - در برخى روش ها كلمه اى كه جندين بر بکاررفت؛ هر بر به شکل جدیدی رمز می شو (بسته به جايكاه کلمه در متن) بيشتر اجراى برس و جو در سمت كاركزار است. تنها رمزتكارى كلمه مورد پرس و جو در سمت کارخواه انجام می شود. نسبت به روش های مبتنی بر شاخص دارای جواب اشتباه کمتری است. پیچید کی محاسباتی بالایی دارند و زمان جستجو در آن ها خطی است. بنابراین در مقیاس بز رگ قابل استفاده نیست. این روش ها بیشتر برای ابزارهایی با جستجوی در مقیاس کوچک (مانند تلفن همراه) مناسب است. پرس و جوهای با شرایط تطبیق دقیق را پاسخ می دهند. پرس وجوی شامل شرایط بازه ای و جستجوی الگوها بر روی داده های رشته ای در این روش سخت است. پرس و جو شامل توابع تجمعی امکان پذیر نیست. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 22:
جستجوی مبتنی بر شاخص اطلاعاتی با نام شاخص همراه با داده رمز شده در سمت کار گزار ذخیره می شود. جستجوی داده با استفاده از شاخص ذخیره شده انجام می گیرد. براي هر عنصر که بخواهد جستجو بر مبنای آن انجام شود. باید یک شاخص تعریف کرد. شاخص نباید اطلاعاتی در مورد داده اصلی را فاش نماید. روش های مختلف تولید شاخص باید از یک سو کارایی پرس و جو و از سوی دیگر عدم سوءاستفاده کار گزار از مقدار شاخص در استنتاج داده اصلی را در نظر بگیرند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 23:
جستجوی مبتنی بر شاخص ‎(Ay, Aj) Aig) *‏ ,92 پایگاه داده رمز نشده به , ۰ ۰ برآ ,,1 ‎R¥, (Counter, Etuple,‏ رآ در پایگاه داده رمز شده نگاشت می شود. ‎Counter‏ کلید اصلی جدول رمز شده. 1۳00016 رمز ‎ee ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎Name ‎Ann 1980 Production 10 Bob io75 | R&D 15 Bob 1985 | Financial 10 Carol | 1980 | Production 20 Ann 1980| Financial 12 David | 1975 | R&D 15 Employeec* Counter | Etuple 1: ] 1 | 5 | 34 | 1 1 15667 + ‏م8‎ x lal? ۸ 2 &(nfeuad!= 0 6 6 2 3 973907321۳7] ‏س | د | 8 | ف‎ | ١ 4 =1vs9e8925 2 ‏ماج ده‎ 5 0 * | »| ١ | ‏1م‎ 9 6 r43arg*5)) ‏ه‎ 1 8 1 1 01 = ‎ ‎ ‎ ‎ ‎ ‎ ‏دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 24:
روش های اصلی مبتنی بر شاخص ‎Bucket Based Index *‏ ‎Hash Based Index *‏ B+ Tree Index ° 41-41 ‏درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى‎ rr 

صفحه 25:
شاخص مبتنی بر ‎dy -Bucket‏ © هاسیگموس و همکارانش مبتنتی بر افزودن شاخص مبتنی بر باکت؛ روشی برای پرس و جو روی داده رمز شده ارائه دادند. * _ردیف‌های هر جدول به طور جداگانه و به کمک یکی از الگوریتم‌های رمزنگاری متقارن. رمز می‌شوند. *_به ازای هر مشخصه که جستجو روی آن انجام می‌شود. یک مشخصه به نام شاخص به جدول اضافه مى كردد. ‎D Title “Author Year‏ ‎[tandbook of Applied Crptographs| —_Alited L Menezes 2001‏ 123 7 3 7 3 ماود عمط 9 2 7 = 86 مقت ‎“inh‏ عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 26:
نحوه تعریف شاخص در روش ‎Bucket‏ 1 برای ایجاد شاخص امن, بازه‌ی داده‌های هر مشخصه به تعدادی زیربازه تقیم می‌شود. - بازه ها نباید اشتراک داشته باشند. ۲ ایجاد بازه‌ها می‌تواند با استفاده از انواع روش‌های تقسیم‌بندی صورت گیرد. - طول رابو - تعداد اعضای برابر ۳ به ه رکدام از بازه‌ها مقداری تعلق می‌گیرد. - می توان از یک تابع تولید اعداد شبه تصادفی استفاده کرد. ب به ازای تمام داده‌هایی که در یک زیربازه قرار می‌گيرند. مقدار تعلق گرفته به زیربازه‌ی آنها در شاخص رمزشده قرار داده می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 27:
مثال - بازه بندی و اعطای شاخص id [name [ salary 3 7 a om ۳0 01010101171125 10 eae 000101101... 12 5 10 ao ‏ست د‎ 010111010... | 8_| 28 Las 110111101...|2 [7 1 emma ia Table 1.2: Encrypted salary table. ۳ 4 8 9 3 2 eo 200 400 600 300 1600 6 7 5 28 11 ‏نك ر تب .لپ تن«‎ A P K P U Z 1 6 2 10 3 salary +1 __® | 2 4, 0 ,_38 درس امنیت پایگاه داده ها - نیمسال دوم تحصیلی ۸۸-۸۷ 

صفحه 28:
پرس وجو در شاخص دهی مبتنی بر ۳001661 * برس وجو در دو مرحله صورت مى كيرد: ‎١‏ کارگزار سعی می کند تا آنجا که امکان دارد پاسخ درستی برگرداند ۲ کارخواه نتیجه‌ی ارسالی کارگزار را رمزکثایی کرده و آنرا بردازش مى كند. * در ,]500 یک پرس و جو می تواند با درخت‌های متفاوت که از نظر نتیجه یکسان هستند. نمایش داده شود. * هاسیگموس جداسازی پرس و جو را (بخشی در سمت کار گزار و بخشی در سمت کارخواه) را با استفاده از درخت پوس وجو انجام داده استد عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 29:
پرس و جو در شاخص دهی مبتنی بر ‎Bucket‏ ‏)2( در روش هاسیگموس, درخت نمايش هر پرس‌وجو به دو قسمت. تقسیم می‌شود. بخش زیر عملگر رم زگشایی: کلیه اعمالی که می تواند در سمت کارگزار انجام شود. ۲ بخش بالای عملگر رم زگشایی: اعمالی که باید در سمت کارخواه انجام شوند. آعمال جبر رابطه‌ای وقتی به زیر عمل رم زگشایی برده می‌شوند باید به آعمال جدیدی که روی داده‌های رمزشده قابل اجرا هستند. تبدیل شوند. هاسیگموس جبر رابطه‌ای جدیدی را برای اعمال روی داده‌های رمزشده تعریف کرد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 30:
بهینه سازی اجرای پرس و جو SELECT name FROM books, keeper WHERE keeper.ID = books.keeping AND Title = applied cryptography" fandbook of * فقط عملگرهایی که در زیر عملگر رم زگشایی هستند قابل اجرا در سمت كار كزار هستند * در اين اجرا هیچ عملگری قابل اجرا به روی > ۳ Oovks. keeper = (Keeper.id seed AEM * سربار ارتباطی و محاسباتی در سمت کارخواه بالا \ ‎J‏ ‏است. * براى افزايش كارآبى بايد سعى كرد تا حد امکان. ۱ عملكرهاى رابطهاى را به زير عملكر رمز كشابى منتقل Oo ‏جروج‎ as Cocks” دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 31:
اجرای بهینه پرس و جو TT. آعمال تا حد امکان باید در سمت کارگزار انجام شود. - ۳ رابطه 5151:5130 روى جدول 800166 به هی وي زير عملكر رمزكشابى برده شده است. لوصا براى بردن اين عملكر به زير عملكر رمزكشابى بايد آنرا تبدیل به 6" که در جبر جدید هاسیگموس برای < 5510۷ روی جداول رمزشده و ‎Keeper’ it‏ < تسا( مشخصه‌های شاخص تعریف شده است. تبدیل کرد. اين اجرا از برس وجو به دلیل اجرای برخی از \ ‎Lo‏ ها در سمت کارگزار اجرای کارایی است. 3 ‎ne‏ كاز اجراي راد 00 تسیا \ a) امم عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 32:
مزایا و معایب روش باکت بندی برای تولید شاخص * روش های مبتنی بر 131201601 برای اجرای شروط تساوی مناسب هستند. - ۵ - ز1 و ۷ - زنه پرس و جوهای بازه ای نیز با کمی تغییر در این روش شاخص دهی قابل اجرا است. ‎A,> v->(1, = B, or B, or ...or -‏ * مثال: - شرط 5213107<50000 در جدول صفحات قبل باید به شکل زیر تبدیل شود: ‎Salary*=2 OR Salary*=10 OR Salary*=3‏ ‎SUM. MIN. MAX. Avg wile crood ela est el oll pus *‏ - - هاسیگموس این روش را تعمیم داد و با استفاده از یک تابع همریخت اختفانی اجرای توابعی مثل جمع و ضرب را فراهم کرد. لان اذك ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 33:
مزایا و معایب روش باکت بندی برای تولید شاخص (۲) * _ وجود مقدار زیادی از داده های اضافی در نتایج کار گزار (به ویژه اگر اعمالی مانند پیوند در پرس و جو وجود داشته باشد) - روش‌هایی برای بهبود و کاهش اشتباه‌های مثبت در روش هاسیگموس ارائه شده است. * اين روش بيشتر برای داده‌های عددی کاربرد دارد و به کار گیری روش برای داده‌های رشته‌ای یا متتی که دامنه‌ی داده‌ها بزرک است. چندان مناسب نیست. - در تعریف بازه برای داده‌های رشته‌ای, ممکن است تعداد زیادی داده در یک بازه قرار گیرد که این خود به معنای ارسال تعداد زیادی داده‌ی اضافی در پاسخ به یک پرس‌وجو و در نتیجه سربار ارتباطی و محاسباتی بالا است. *_اگر بازه ها طوری ساخته شوند که مثلاً در هر بازه یک مقدار قرار بگیرد امکان تحلیل فر کانسی وجود دارد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 34:
شاخص مبتنی بر توابع درهم ساز از مفهوم توابع درهم ساز برای ساختن شاخص استفاده می شود. برای ساخت شاخص در این روش- داده‌ها توسط یک تابع درهم‌ساز دارای تصادم دسته‌بندی می‌شوند. مزیت این نوع شاخص دهی نسبت به روش باکت بندی این است. که دسته‌بندی روی داده‌های پشت سرهم انجام نمی‌شود که این می‌تواند باعث افزایش امنیت گردد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 35:
شاخص مبتنی بر توابع درهم ساز (۲) + اکر تدرابطه ای‌با اسکیمای (,ب , ۰ ۰ ۰ رون ‎(Ay,‏ ترابطه متناظر رمز شده آن باشد, برای هر صفت ‎Ay‏ در ,18 که بخواهیم برای آن شاخص تعریف کنیم. تلبع درهم ساز تعریف می شود که ور دامنه رب و 88 دامنه شاخص 1 متناظر با زب است. ‎for all x, y in Dy; if x = y then h@)= h(y)‏ + * برد «از دامنه آن کوچکتر است . - امکان برخورد وجود دارد. ۰ برای هر دو مقدار تصادفی متفاوت ولی نزد (ع۰ توزیع احتمالی (00 - (20 یکنواخت است. به هم ۲ و ودر دامته >| ۷ — ‎D, (1x‏ - تابع درهم ساز ترتیب خصیصه در دامنه را حفظ نمی کند. ‎ai‏ ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 36:
شاخص مبتنی بر توابع درهم ساز - ویژگی ها * اجرای پرس و جوهای تساوی (مانند روش های شاخص دهی مبتنی بر 001661) ممکن است. - هر شرط فا به شرط (7)[-1 که و1 شاخص متناظر با ژفظ در جدول رمز شده است: تبدیل می شود. برخورد در توابع درهم ساز باعث ارسال چندتایی های اضافی به سمت کار خواه می شود. تابع درهم ساز فاقد برخورد مشکل ارسال نتایج زیادی به کارخواه را رفع می کند ولی احتمال تحليل هاى فر كانسى را افزايش مى دهد. مشکل اصلی روش های شاخص دهی مبتنی بر تولبع درهم ساز عدم پشتیبانی از پرس و جوهای بازه ای است. - دامیانی و همکارانش برای اضافه کردن قابلیت انجام جستجوی بازه‌ای به این روش از شاخص مبتنی بر درخت 18+ در كنار اين نوع شاخص دهى استفاده کردند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 37:
شاخص مبتنی بر درخت 18+ یکی از روش های شاخص دهی استفاده از ساختار داده ای درخت 13+ است. در درخت 13+ کره های داخلی به طور مستقیم به چندتایی ها در پایگاه داده اشاره نمی کنند بلكه به سایرگره ها در ساختار اشاره می نمایند. ره های برک متقیماًبه چندتایی هایی در پایگاه داده با مقادیر مشخص برای صفت شاخص اشاره می کنند. درخت 33+ می تواند برای هر صفت رب در اسکیمای ,18 که در شروط پرس و جو ظاهر می شود, تعریف شود. شاخص توسط کارخواه روی مقادیر رمز نشده صفت ساخته شده و سپس روی کارگزار همراه با پایگاه داده رمز شده ذخیره می کردد. ساختار درخت 13+به جدهلی با دو صفت شناسه کره و محتوای ره تبدیل می شود. این جدول برای هر گره یک ردیف دارد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 38:
Gq ay الل ‎Id | VertexContent. 101 |‏ ‎Carol, 3 1 gtem945/*e‏ ,2 1 سوه | 2 5 ‎Bob,‏ ,4 | 2 ‎David, 7 3. | ue63/)iw‏ ,6 | 3 ‎Ann, 5,1, 5 a_| 8/*5sym,p‏ | 4 ‎Bob, 6, 2.3 5 mw 39wiol‏ 5 ‎Garol, 7,4 6 | =weo2I'ps‏ |_6 ‎David, NIL, 6 7 oieb5S (ps*‏ 7 Carol Bob David Ann |- Bob { ‏ای‎ {Davia | درس امنیت پایگاه داده ها- نیمسال دوم تعصیلی ۸۸-۸۷ 

صفحه 39:
روش ارزیابی پرس و جو در درخت 18+ فرض کنید. کارخواه اجرای پرس‌وجویی با شرط ۲ < ۸ را درخواست کرده که ۲ یک مقدار ثابت است. کارخواه باید درخت 8 ذخیره شده روی کارگزار را برای یافتن محل ۷ پیمایش کند. - کارخواه درخواستی برای دریافت ریشه‌ی درخت ظ انجام می‌دهد.(ریشه‌ی درخت. ردیف با شماره‌ی ۱ است.) این ردیف به کارخواه ارسال و در آنجا رم زگشایی و پردازش می‌شود. - با توجه به مقدار ۷ گره‌ی بعدی که باید پیمایش شود انتخاب شده و درخواستی مبنی بر ارسال آن گره به کارگزار فرستاده می‌شود. این روند تا پیدا کردن برگ حاوی 7 ادامه يبدا مى کند. بس از پیدا شدن 7 تمام برگ‌های بعد از آن به سمت کارخواه ارسال می‌شوند. اين گره‌ها در سمت کارخواه رمزگشایی شده و شماره‌ی ر کوردهای مورد نظر پیدا شده به سمت کارگزار ارسال می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 40:
شاخص مبتنی بر درخت 3+ ویژگی ها ۶ درخت 18+ در پاسخ به پرس و جو چندتایی اضافی به سمت. کارخواه نمی فرستد. هزینه ارزیابی شرایط پرس و جو برای کارخواه نسست به روش های مبتنی بر باکت و توابع درهم ساز بسیار بیشتر است. - به همين دليل معمولاً درخت 33+ را در کنار یکی از روش های شاخص دهی مبتنی بر باکت یا توابع در هم ساز بكار برده و از درخت 15+ تنها در هنكام ارزيابى بازه ها در برس و جو ها استفاده مى نمايند. * با توجه به اين كه محتواى درخت 19+ در سمته کا رگزار رمزنگاری شده استه اين روش در برابر حملات استنتاجى نيز مقاوم اسهد عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 41:
جستجوی مبتنی بر شاخص در داده های رشته ای روشی مبتنی بر شاخص برای پرس و جو روی داده های رشته ای توسط ۲۱۷۵ ارائه شده است (۲۰۰۶). * با استفاده از روش وانگ. می‌توان به جستجوی الگوهای دلخواه در داده‌هایي رمزشده پرداخت. * ریزدانگی رمزنگاری در روش ۰۷۷۵10 در سطح فیلد است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 42:
مراحل رمزنگاری به هر رشته 5 که از م کاراکتر ,© طول «: بيت اختصاص داده می‌شود. (©>,ر© تشکیل شده است. مقدار شاخصی به هر رشتهى م6©... 6 © > 5 به رشته‌ی و رر5...رکرک <51 که در آن وبرنار6 استه بسط داده می‌شود. با استفاده از تابع درهم‌ساز ظ مقداری بین ۰ تال برای هر کدام از ,5 ها به دسلته مى آيد. 1 اگر مقدار (5) 12 برابر با ۶ باشد. در آن صورت بيت شماره #ام در شاخص مربوطه برابر با یک می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 43:
مثال * §1= (abcehklst) ۰ 60 ‏؟ء تابعی در هم ساز دوتایی های ۵۳0.06 .... و 51 را به عددی بین ۰ تا ۱۵ نگاشت.‎ ‏می کند.‎ S2=Index(abcehklst)= (0010100010101001), ۰ * هشت رشته ۲ تایی وجود دارد در حالیکه 1 بیت یک در 52 دیده می شود. یعنی برخی از کارا کترهای دوتایی به یک مقدار توسط « نگاشت می شوند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 44:
روش جستجو ‎0.١‏ مقدار رشته‌ای موجود در الگوی رشته ای مورد پرس و جو بسط داده می‌شود و مقادیر اختصاص داده شده توسط تابع ۶ به هر دو حرف متوالی آن به دست می‌آید. - . پرس و جو روی مقدار رشته ای به پرس و جو روی شاخص (رشته بیتی) تبدیل می شود. ۲ مقادیر به دست آمده مکان بیت‌هایی از مقادیر شاخص را كه بايد ۱ باشند تا شرط پرس وجو ارضاء شود, مشخص می کند. این مقادیر به سمت کار گزار ارسال می‌شوند. ۳ کارگزار به ازای هر مقدار شاخص, مقادیر بیت‌های آن در مکان‌های ارسال شده را بررسی می کند. اگر همه دارای مقدار ۱ بودند؛ مقدار شاخص را به عنوان یکی از جواب‌ها به سمت کارخواه برمی گرداند. ‎ -‏ در جواب های ارسال شده ممکن است نتایج اضافی وجود داشته باشد که باید توسط ‏کارخواه مجدداً پردازش شده تا جواب دقیق به دست آید. ‎ ‎ ‏عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 45:
حالت های مختلف پرس و جوی رشته ای ‎١‏ تطبیق دقیق ‎gs) attribute=value b,5‏ جدول رمز نثده تبديل مى 995 4 ~ ‎a* index (value) a*‏ مقدار رمز شده 2131190016 در سمت کارگزار است. 5 تطبیق الگویی شرط ‎Jgve so attribute LIKE value‏ )30 نشده: تشه ‎alike cOc1...ck => (€@)qo=1 AND (@)ine1)=1 AND ... AND‏ ‎reay=1)‏ ‏پرس و جوی با شرایط بولی ‎(attribute=value 1) OR (attribute=value 2), (attribute like value 1) AND (attribute like value 2), (attribute like value 1) AND NOT (attribute like value 2) ‏- از حالت اول و دوم قابل استنتاج است. ‏۱ ‏۴ درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 ‎1 ‎5 ‎ 

صفحه 46:
مثال eid aia awe [ Sex. 021021 | Chessbasketball | 24 M 021094 | basketballcook 50 | F 021005 | Languageschat 26 | 35 021096 | programnotwork | M 1 13 ‏رد‎ aid 021021 | 100101011001001001011... ] 21121913 1 021094 | 100111100110000110101-.. |] 0 218801 0210 0 1 26 M 211929060 021006 ۱ 1100 21 1 21192011160 select eid, age from employee where did like ‘chess select * from employee" where ) ad (ig =D) ad ‏هه‎ دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 47:
تحلیل روش * در این روش, در صورتی که طول 102 بزرک انتخاب شود. حمله متن اصلی معلوم محتمل است. - هر زوج کارا کترجه مقدار یکتلیی در شاخص منتسب می شهند و امکان تحلیل فر کانسی و شکستن شاخص وجود دارد. * در صورت کوچک بودن سس تعداد زیادی داده اشتباه به سمت کارخواه ارسال خواهد شد. * در جدول رمز شده فیلد اضافه ای برای شاخص بلید در نظر گرفته شود که حجم ‎OT‏ ‏به اندازه شاخص ( «) وابسته است. - در صورتی که « فیلد نیاز به رمز شدن داشته و طول شاخص به طور متوسط «« بیت ‎ASL‏ میزان فضای اضافی مورد نیاز 100*90 بیت برای شاخص است. لان اذك 41-41 ‏درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى‎ ry oi 

صفحه 48:
جمع بندی روش ها ی مبتنی بر شاخص زیادی روی این گونه روش ها صورت گرفته و دارای زمینه تنوریک قوی می باشند. حتی دارای جبر رابطه ای مخصوص می باشند. بیشتر فرایند اجرای پرس و جو بر روی کار گزار متم رکز است. * _ هزینه ذخیره سازی تقریباً دو برابر ذخیره سازی معمولی است. زیرا غیر از مقدار رمز شده ذخیره: مقدار ز ذخیره می کردد. ‎ *‏ امکان استتتاج و افشای اطلاعات وجود دارد که میزان آن وابسته بهتعریف شاخص است. - ۰ 12۷0016000۷ و همعارانشثانکرده‌اند کسه تسقریاً تسم روش‌هایمبتن‌سر شاخموو لمسیستند بسه ود روشهاییکه در پساسخ بسه پسرس‌وجو چندتابیهعاضافیتسولید نمی‌کسندد در معرض‌تسهد بدلفثای لمطلاعاتقرار دايند * برس و جوهاى شامل بيوند در اين روش قابل اعمال است. * برس و جوهاى تساوى. و الكوبى براى داده هاى عددى و رشته اى قابل انجام است. * امكان اجراى برس و جوهاى بازه اى بسته به تعريف شاخص دارد. * امكان اجراى برس و جوهاى شامل توابع تجمعى وجود ندارد. * چون‌با تغیبر توزیع داده ها نیز به دسته بندی مجدد داده ها برای تعریف شاخص وجود دارد. این روش بشتر برای داده های فقط خواندنی مناسب است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 49:
روش های مبتنی بر کاربرد توابع همریخت اختفایی * _توابع همریخت اختفایی نوعی توابع برای رمزنگاری است. * در روش رمزنگاری همریخت اختفایی (عنطم :هط ۳۳۷۵0۲)؛ حاصل انجام یک ‎foc‏ روی داده‌های رمزشده؛ معادل رمزشده حاصل عملی دیگر روی داده‌های اصلی است. ۴((رییه) ع ( رمع ‎٠‏ - E() . E(y) = E(xty) *_بوسیله‌ی توابع رمزنگاری همریخت اختفائی می‌توان برخی از عملیات مانند جمع و ضرب را به طور مستقیم روی داده‌های رمزشده انجام داد. * فیلدهایی را که روی آنها پرس و جوی تجمعی اجرا می شود. با استفاده از رمزنگاری همریخت رمز می کنند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 50:
روش هاسیگکموس * هاسیگموس با استفاده از یک تابع رمزنگاری همریخت اختفانی که دو خاصیت جمعی و ضربی را پثتیبانی می کند, توابع جمع و ضرب را روی داده‌های رمزشده اجرا کرد. ۶ خواص تابع رمزنگاری همومورفیسم استفاده شده: - کلید رمزنگاری (6 ,)12 که « و و به وسیله کاربر تعیین مى شوند. که به کارگزار دادم میشود ۲.6 ‎(mod p)‏ 21 دوو - ‎pp? = 1 (mod q)‏ - Dy(er.c2) = (cy mod p)qg7! + (co mod q)pp~! (mod n) دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 51:
مثال p=5,q=7 n=p.q=35 k=(5, 7) * مى خواهیم 8 < ره و 12 < ره را جمع کنیم ‎Efa,) = )3,1(‏ ‎Efa,) = (2,5)‏ ‎E (al) + E (a2) = (3+2, 1+5) = (5, 6)‏ ‎D (5, 6) = «qq? + &pp (mod 35)‏ = (5*7*3 + 6*5*3) (mod 35) =195 (mod 35) = 20 دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 52:
مشکل استنتاج * _استفاده از تابع رمزنگاری همریخت اختفائی معرفی شده کاملاً امن نیست و کار گزار می‌تواند مقدار اصلی برخی از مقادیر رمزشده را به دست آورد. - فرض كنيد, » و و دو عدد باشند که به صورت ‎Wy Vy) 9 (Kp Xs)‏ 509 شده‌اند. اگر تست باشد. رابطه‌ی تکرام نیز بین مقادیر رمزشده این متفیرها وجود دارد. در چنین حالتی کاوگزار می‌تواند مقادیر اصلی این متتبرها را به دست آورد. کارگزار شروع به جمع ‎Ky OOS‏ ركة) با خودش مى كند و اين كار را آنقدر ادامه می‌دهد تا نتيجه آن با 2 رت) برابر شود. تعداد این جمع کردن‌ها باب با عدد ار است. (پشدیه) + (مشیت) < (معیع) * هاسيكموس با اضافه كردن نويز تصادفى به وتو دزی پر و ونم ‎Rep.‏ یک تابع شبه تصادفی است. * نويز در هنگام رم زکشایی از داده‌ها حذف می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 53:
روش های رمزنگاری مبتنی بر حفظ ترتیب * در روش های رمزنگاری با حفظ 5 ‎cots (Order Preserving) U4‏ هابه كونه اى رمز می شوند که ترتیب داده ها پس از رمز شدن با ترتیب داده های اصلی یکسان باشد. * این نوع رمزنگاری برای اجرای پرس و جو های بازه ای مناسب است. * آگراوال برای رمزنگاری داده های عددی و اجرای پرس و جوهای بازه ای روی آنها از این روش استفاده کرده است. *_ فرض کنید. داده‌های اصلی دارای توزیع اولیه ۸ هستند. این داده‌ها به نحوی رمز می‌شوند. که علاوه بر حفظ ترتیب از توزیع دلخواه ۸4 تبعیت کنند. - ابتدا داده‌ها به توزیع یکنواخت ۶ نگاشت شده و سپس توزیع / به توزیع هدف ۸4 نگاشت می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 54:
مراحل رمزنگاری ۰ 028:5 در سه مرحله كار ميكد (0تأتكدعوع22 02061 ‎(Encryption Scheme‏ ‎Jue)‏ کردن: داده‌های اصلی به تعدادی دسته تقیم می‌شوند و توزیع داده‌های هر دسته مدل می‌شود. ‏روش هایی برای تعیین تعداد دسته ها و طول هر دسته وجود دارد. ‎ ‎ ‏02 افزایش دسته‌ها منجر به افزایش هزینه‌های مدل می‌شود. ۲ سطح کردن: داده‌های اصلی ۶ به داده‌های مسطح "1 به قسمی تبدیل شود که مقادیر 2 دارای توزیع یکنواخت باشند. * .در مرحل‌ی سطح کردن برای هر دسته. یک تابع تگاشت 17 ایجاد می‌شود. تابع ۸ هر دسته را به دسته‌ای با توزیع یکنواخت نگاشت می کند. ‏دو مقدار متفاوت در داده های اصلی هميشه به دو مقدار متفاوت از فضای مسطح شده تگاشت شوند. ‎ ‏اده‌های سطح "۸ به داده‌های رمزشده 6 تبدیل می‌شود, به قسمی که مقادیر 6 دارای توزیع نهایی که برای داده‌های رمزشده در نظر گرفته شده بود. باشند. ‎ ‏عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 55:
درس امنیت پایگاه داده ها- نیمسال دوم تعصیلی ۸۸-۸۷ 

صفحه 56:
ویژگی های روش رمزنگاری با حفظ ترتیب * اجرای پرس و جوها در اين روش چندتایی های اضافی جه سمت کارخواه ارسال نمی کند. * امنیت در این روش زملنی تامین می شود که کار گزار احمله کننده اطلاعاتی در مورد پایگاه داده اصلی و يا دامنه صفت ها نداشته باشد. - این روش در مقابل حمله متن اصلی معلوم آسیب پذیر است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 57:
پایگاه داده ها - تیمسال دوم تحصیلی ۸۸-۸۷