এমন একটি পরিস্থিতি বিবেচনা করুন যেখানে আপনাকে একটি ব্যাঙ্ক ভল্ট সুরক্ষিত করতে হবে। এটি একটি চাবি ছাড়া একেবারে দুর্ভেদ্য বলে মনে করা হয়, যা আপনাকে কাজের প্রথম দিনেই দেওয়া হয়। আপনার লক্ষ্য নিরাপদে কী সংরক্ষণ করা হয়.

ধরা যাক যে আপনি চাবিটি সর্বদা আপনার কাছে রাখার সিদ্ধান্ত নিয়েছেন, প্রয়োজন অনুসারে সঞ্চয়স্থানে অ্যাক্সেস প্রদান করবেন। কিন্তু আপনি দ্রুত বুঝতে পারবেন যে এই জাতীয় সমাধানটি অনুশীলনে ভালভাবে পরিমাপ করে না, কারণ আপনি যখনই স্টোরেজ খুলবেন তখন আপনার শারীরিক উপস্থিতি প্রয়োজন। আপনি যে ছুটির প্রতিশ্রুতি দিয়েছিলেন সে সম্পর্কে কী? এছাড়াও, প্রশ্নটি আরও ভয়ঙ্কর: আপনি যদি আপনার একমাত্র চাবিটি হারিয়ে ফেলেন তবে কী করবেন?

আপনার ছুটির কথা মাথায় রেখে, আপনি চাবির একটি অনুলিপি তৈরি করার এবং অন্য কর্মচারীর কাছে এটি অর্পণ করার সিদ্ধান্ত নেন। যাইহোক, আপনি বুঝতে পারেন যে এটিও আদর্শ নয়। চাবির সংখ্যা দ্বিগুণ করে, আপনি চাবি চুরির সম্ভাবনাও দ্বিগুণ করেন।

হতাশায়, আপনি ডুপ্লিকেটটি ধ্বংস করেন এবং আসল কীটি অর্ধেক ভাগ করার সিদ্ধান্ত নেন। এখন, আপনি ভাববেন যে চাবির টুকরো সহ দুই বিশ্বস্ত লোককে চাবি সংগ্রহ করতে এবং ভল্ট খুলতে শারীরিকভাবে উপস্থিত থাকতে হবে। এর মানে হল যে একজন চোরকে দুটি টুকরো চুরি করতে হবে, যা একটি চাবি চুরি করার চেয়ে দ্বিগুণ কঠিন। যাইহোক, আপনি শীঘ্রই বুঝতে পারবেন যে এই স্কিমটি শুধুমাত্র একটি চাবির চেয়ে বেশি ভালো নয়, কারণ কেউ যদি অর্ধেক চাবি হারিয়ে ফেলে, তাহলে পুরো চাবিটি পুনরুদ্ধার করা যাবে না।

সমস্যাটি অতিরিক্ত কী এবং লকগুলির একটি সিরিজ দিয়ে সমাধান করা যেতে পারে, তবে এই পদ্ধতির দ্রুত প্রয়োজন হবে много চাবি এবং তালা। আপনি সিদ্ধান্ত নিন যে আদর্শ নকশাটি হবে কী ভাগ করে নেওয়া যাতে নিরাপত্তা সম্পূর্ণরূপে একজন ব্যক্তির উপর নির্ভর না করে। আপনি এও উপসংহারে পৌঁছেছেন যে খণ্ডের সংখ্যার জন্য অবশ্যই কিছু থ্রেশহোল্ড থাকতে হবে যাতে একটি খণ্ডটি হারিয়ে গেলে (বা যদি কোনও ব্যক্তি ছুটিতে যায়), পুরো কীটি কার্যকর থাকে।

কিভাবে একটি গোপন ভাগ

1979 সালে আদি শামির যখন তার কাজ প্রকাশ করেন তখন এই ধরনের কী ব্যবস্থাপনা পরিকল্পনার কথা চিন্তা করেছিলেন "কীভাবে একটি গোপনীয়তা শেয়ার করবেন". নিবন্ধটি সংক্ষিপ্তভাবে তথাকথিত ব্যাখ্যা করে একটি গোপন মান (যেমন একটি ক্রিপ্টোগ্রাফিক কী) দক্ষতার সাথে ভাগ করার জন্য থ্রেশহোল্ড স্কিম অংশ তারপর, যখন এবং শুধুমাত্র যখন অন্তত থেকে অংশগুলি একত্রিত হয়, আপনি সহজেই গোপনটি পুনরুদ্ধার করতে পারেন .

নিরাপত্তার দৃষ্টিকোণ থেকে, এই স্কিমের একটি গুরুত্বপূর্ণ বৈশিষ্ট্য হল যে আক্রমণকারীর একেবারে কিছুই জানা উচিত নয় যদি না তার অন্তত অংশ এমনকি উপস্থিতি অংশ কোন তথ্য প্রদান করা উচিত নয়. আমরা এই সম্পত্তি কল শব্দার্থগত নিরাপত্তা.

বহুপদী ইন্টারপোলেশন

শামির থ্রেশহোল্ড স্কিম ধারণার চারপাশে নির্মিত বহুপদী ইন্টারপোলেশন. আপনি যদি এই ধারণার সাথে পরিচিত না হন তবে এটি আসলে বেশ সহজ। প্রকৃতপক্ষে, আপনি যদি কখনও একটি গ্রাফে পয়েন্ট আঁকেন এবং তারপর সেগুলিকে লাইন বা বক্ররেখা দিয়ে সংযুক্ত করেন, আপনি ইতিমধ্যেই এটি ব্যবহার করেছেন!

দুটি পয়েন্টের মাধ্যমে আপনি ডিগ্রী 2 এর সীমাহীন সংখ্যক বহুপদ আঁকতে পারেন। তাদের থেকে শুধুমাত্র একটি বেছে নিতে আপনার একটি তৃতীয় বিন্দু প্রয়োজন। চিত্রণ: উইকিপিডিয়া

এক ডিগ্রি সহ একটি বহুপদ বিবেচনা করুন, . আপনি যদি একটি গ্রাফে এই ফাংশনটি প্লট করতে চান, আপনার কত পয়েন্ট দরকার? ঠিক আছে, আমরা জানি যে এটি একটি রৈখিক ফাংশন যা একটি লাইন গঠন করে এবং তাই এটির অন্তত দুটি পয়েন্ট প্রয়োজন। এরপরে, ডিগ্রি দুই সহ একটি বহুপদ ফাংশন বিবেচনা করুন, . এটি একটি দ্বিঘাত ফাংশন, তাই গ্রাফটি প্লট করার জন্য কমপক্ষে তিনটি পয়েন্ট প্রয়োজন। ডিগ্রী তিন সহ একটি বহুপদ সম্পর্কে কিভাবে? অন্তত চার পয়েন্ট। এবং তাই এবং তাই ঘোষণা.

এই সম্পত্তি সম্পর্কে সত্যিই চমৎকার জিনিস যে, বহুপদী ফাংশন ডিগ্রী দেওয়া এবং অন্তত পয়েন্ট, আমরা এই বহুপদী ফাংশনের জন্য অতিরিক্ত পয়েন্ট বের করতে পারি। এই অতিরিক্ত বিন্দুগুলোর এক্সট্রাপোলেশনকে আমরা বলি বহুপদী ইন্টারপোলেশন.

একটি গোপন আপ করা

আপনি হয়তো ইতিমধ্যেই বুঝতে পেরেছেন যে এখানেই শামিরের চতুর পরিকল্পনাটি কার্যকর হয়। আসুন আমাদের গোপন কথা বলি - এটা . আমরা ঘুরতে পারি গ্রাফের একটি বিন্দুতে এবং ডিগ্রি সহ একটি বহুপদ ফাংশন নিয়ে আসা , যা এই বিন্দু সন্তুষ্ট. আমাদের আপনাকে মনে করিয়ে দেওয়া যাক আমাদের প্রয়োজনীয় খণ্ডের থ্রেশহোল্ড হবে, তাই যদি আমরা থ্রেশহোল্ডকে তিনটি খণ্ডে সেট করি, তাহলে আমাদের অবশ্যই ডিগ্রী দুই সহ একটি বহুপদী ফাংশন বেছে নিতে হবে।

আমাদের বহুপদীর ফর্ম থাকবে যেখানে и — এলোমেলোভাবে নির্বাচিত ধনাত্মক পূর্ণসংখ্যা। আমরা শুধু ডিগ্রী সহ একটি বহুপদ নির্মাণ করছি , যেখানে বিনামূল্যে সহগ  - এই আমাদের গোপন , এবং পরবর্তী প্রতিটির জন্য শর্তাবলী একটি এলোমেলোভাবে নির্বাচিত ধনাত্মক সহগ আছে। আমরা যদি মূল উদাহরণে ফিরে যাই এবং ধরে নিই , তারপর আমরা ফাংশন পেতে .

এই মুহুর্তে আমরা সংযোগ করে টুকরা তৈরি করতে পারি অনন্য পূর্ণসংখ্যা যেখানে (কারণ এটা আমাদের গোপন)। এই উদাহরণে, আমরা তিনটির থ্রেশহোল্ড সহ চারটি খণ্ড বিতরণ করতে চাই, তাই আমরা এলোমেলোভাবে পয়েন্ট তৈরি করি এবং চারটি বিশ্বস্ত লোকের প্রত্যেকের কাছে একটি করে পয়েন্ট পাঠান, চাবির রক্ষক। এটাও আমরা মানুষকে জানিয়েছি , যেহেতু এটি সর্বজনীন তথ্য হিসাবে বিবেচিত হয় এবং পুনরুদ্ধারের জন্য প্রয়োজনীয় .

রহস্য উদ্ধার

আমরা ইতিমধ্যে বহুপদী ইন্টারপোলেশনের ধারণা নিয়ে আলোচনা করেছি এবং এটি কীভাবে শামিরের থ্রেশহোল্ড স্কিমকে অন্তর্নিহিত করে। . চার ট্রাস্টির মধ্যে যে কোনো তিনজন পুনরুদ্ধার করতে চাইলে , তারা শুধুমাত্র interpolate প্রয়োজন তার নিজস্ব অনন্য পয়েন্ট সঙ্গে. এটি করার জন্য, তারা তাদের পয়েন্ট নির্ধারণ করতে পারেন এবং নিম্নলিখিত সূত্র ব্যবহার করে Lagrange ইন্টারপোলেশন বহুপদী গণনা করুন। যদি প্রোগ্রামিং আপনার কাছে গণিতের চেয়ে পরিষ্কার হয়, তাহলে পাই মূলত একটি অপারেটর for, যা সমস্ত ফলাফলকে গুণ করে এবং সিগমা হয় for, যা সবকিছু যোগ করে।

এ আমরা এটিকে এভাবে সমাধান করতে পারি এবং আমাদের মূল বহুপদী ফাংশন ফিরিয়ে দিতে পারি:

যেহেতু আমরা জানি , পুনরুদ্ধার সহজভাবে করা:

অনিরাপদ পূর্ণসংখ্যা পাটিগণিত ব্যবহার করে

যদিও আমরা সফলভাবে শামির মৌলিক ধারণা প্রয়োগ করেছি , আমরা এখন পর্যন্ত উপেক্ষা করা একটি সমস্যা সঙ্গে বাকি আছে. আমাদের বহুপদী ফাংশন অনিরাপদ পূর্ণসংখ্যা পাটিগণিত ব্যবহার করে। লক্ষ্য করুন যে প্রতিটি অতিরিক্ত পয়েন্টের জন্য একজন আক্রমণকারী আমাদের ফাংশনের গ্রাফে প্রাপ্ত করে, অন্যান্য পয়েন্টগুলির জন্য কম সম্ভাবনা রয়েছে। আপনি যখন পূর্ণসংখ্যার গাণিতিক ব্যবহার করে একটি বহুপদী ফাংশনের জন্য ক্রমবর্ধমান সংখ্যক বিন্দুর পরিকল্পনা করবেন তখন আপনি নিজের চোখে এটি দেখতে পাবেন। এটি আমাদের উল্লিখিত নিরাপত্তা লক্ষ্যের বিপরীত, কারণ আক্রমণকারীর একেবারে কিছুই জানা উচিত নয় যতক্ষণ না তারা কমপক্ষে টুকরা

পূর্ণসংখ্যার গাণিতিক সার্কিট কতটা দুর্বল তা প্রদর্শন করতে, এমন একটি দৃশ্য বিবেচনা করুন যেখানে একজন আক্রমণকারী দুটি পয়েন্ট পেয়েছে এবং পাবলিক তথ্য জানে যে . এই তথ্য থেকে তিনি অনুমান করতে পারেন , দুই এর সমান, এবং সূত্রে পরিচিত মানগুলি প্লাগ করুন и .

হামলাকারী তখন খুঁজে বের করতে পারে , গণনা :

যেহেতু আমরা সংজ্ঞায়িত করেছি এলোমেলোভাবে নির্বাচিত ধনাত্মক পূর্ণসংখ্যা হিসাবে, সম্ভাব্য সীমিত সংখ্যক রয়েছে . এই তথ্য ব্যবহার করে, একজন আক্রমণকারী অনুমান করতে পারে , যেহেতু 5-এর বেশি কিছু করতে হবে নেতিবাচক. এটা সত্য হতে সক্রিয় আউট যেহেতু আমরা নির্ধারণ করেছি

আক্রমণকারী তারপর সম্ভাব্য মান গণনা করতে পারেন প্রতিস্থাপন в :

জন্য সীমিত বিকল্প সঙ্গে এটি স্পষ্ট হয়ে যায় যে মানগুলি নির্বাচন করা এবং পরীক্ষা করা কতটা সহজ . এখানে মাত্র পাঁচটি বিকল্প আছে।

অনিরাপদ পূর্ণসংখ্যা গাণিতিক দিয়ে সমস্যা সমাধান করা

এই দুর্বলতা দূর করতে, শামির মডুলার পাটিগণিত ব্যবহার করে প্রতিস্থাপনের পরামর্শ দেন উপর যেখানে и — সমস্ত মৌলিক সংখ্যার সেট।

আসুন দ্রুত মনে করি কিভাবে মডুলার পাটিগণিত কাজ করে। হাত দিয়ে ঘড়ি একটি পরিচিত ধারণা। তিনি একটি ঘড়ি ব্যবহার করেন যে . ঘন্টার হাত বারোটা পেরিয়ে গেলেই একটাতে ফিরে আসে। এই সিস্টেমের একটি আকর্ষণীয় বৈশিষ্ট্য হল যে কেবল ঘড়ির দিকে তাকালে আমরা অনুমান করতে পারি না যে ঘন্টার হাত কতগুলি আবর্তন করেছে। যাইহোক, যদি আমরা জানি যে ঘন্টার হাতটি 12টি চারবার পেরিয়ে গেছে, তাহলে আমরা একটি সাধারণ সূত্র ব্যবহার করে কত ঘন্টা কেটেছে তা সম্পূর্ণরূপে নির্ধারণ করতে পারি। যেখানে  আমাদের ভাজক (এখানে ),  সহগ (এখানে কতবার ভাজক একটি অবশিষ্ট ছাড়া আসল সংখ্যায় যায় ), এবং  অবশিষ্টাংশ, যা সাধারণত একটি মডুলো অপারেটর কল ফেরত দেয় (এখানে ) এই সমস্ত মানগুলি জানা আমাদের জন্য সমীকরণটি সমাধান করতে দেয় , কিন্তু যদি আমরা সহগ মিস করি, আমরা কখনই মূল মান পুনরুদ্ধার করতে সক্ষম হব না।

আমরা আমাদের পূর্ববর্তী উদাহরণে স্কিমটি প্রয়োগ করে এবং ব্যবহার করে এটি কীভাবে আমাদের স্কিমের নিরাপত্তা উন্নত করে তা প্রদর্শন করতে পারি . আমাদের নতুন বহুপদী ফাংশন , এবং নতুন পয়েন্ট . এখন মূল রক্ষক আমাদের ফাংশন পুনর্গঠন করার জন্য আবার বহুপদী ইন্টারপোলেশন ব্যবহার করতে পারে, শুধুমাত্র এই সময়ে যোগ এবং গুণের ক্রিয়াকলাপগুলি মডুলো হ্রাসের সাথে থাকতে হবে (যেমন ).

এই নতুন উদাহরণ ব্যবহার করে, ধরা যাক যে আক্রমণকারী এই দুটি নতুন পয়েন্ট শিখেছে, , এবং জনসাধারণের তথ্য . এই সময়, আক্রমণকারী, তার কাছে থাকা সমস্ত তথ্যের উপর ভিত্তি করে, নিম্নলিখিত ফাংশনগুলি আউটপুট করে, যেখানে  সমস্ত ধনাত্মক পূর্ণসংখ্যার সেট, এবং মডুলাস সহগ প্রতিনিধিত্ব করে .

এখন আমাদের আক্রমণকারী আবার খুঁজে পায় , গণনা করা :

তারপর আবার চেষ্টা করে প্রতিস্থাপন в :

এবার তার একটা গুরুতর সমস্যা। সূত্র অনুপস্থিত মান , и . যেহেতু এই ভেরিয়েবলগুলির একটি অসীম সংখ্যক সংমিশ্রণ রয়েছে, তাই তিনি কোনও অতিরিক্ত তথ্য পেতে পারেন না।

নিরাপত্তা বিবেচনা

শামির গোপন শেয়ারিং স্কিম পরামর্শ দেয় তথ্য তত্ত্বের দৃষ্টিকোণ থেকে নিরাপত্তা. এর মানে হল যে গণিত সীমাহীন কম্পিউটিং শক্তি সহ আক্রমণকারীর বিরুদ্ধেও প্রতিরোধী। যাইহোক, সার্কিটে এখনও বেশ কয়েকটি পরিচিত সমস্যা রয়েছে।

উদাহরণস্বরূপ, শামির পরিকল্পনা তৈরি করে না টুকরা চেক করা হবে, অর্থাৎ, মানুষ অবাধে জাল টুকরা উপস্থাপন করতে পারে এবং সঠিক গোপন পুনরুদ্ধারের সাথে হস্তক্ষেপ করতে পারে। পর্যাপ্ত তথ্য সহ একটি প্রতিকূল ফ্র্যাগমেন্ট রক্ষক এমনকি পরিবর্তন করে আরেকটি খণ্ড তৈরি করতে পারে আপনার নিজের বিবেচনার ভিত্তিতে। এই সমস্যাটি ব্যবহার করে সমাধান করা হয় যাচাইযোগ্য গোপন শেয়ারিং স্কিম, যেমন ফেল্ডম্যানের স্কিম।

আরেকটি সমস্যা হল যে কোনো খণ্ডের দৈর্ঘ্য সংশ্লিষ্ট গোপনের দৈর্ঘ্যের সমান, তাই গোপনটির দৈর্ঘ্য নির্ণয় করা সহজ। এই সমস্যাটি তুচ্ছ দ্বারা সমাধান করা যেতে পারে প্যাডিং একটি নির্দিষ্ট দৈর্ঘ্য পর্যন্ত নির্বিচারে সংখ্যা সহ গোপন।

অবশেষে, এটা মনে রাখা গুরুত্বপূর্ণ যে আমাদের নিরাপত্তা উদ্বেগগুলি ডিজাইনের বাইরেও প্রসারিত হতে পারে। বাস্তব-বিশ্বের ক্রিপ্টোগ্রাফিক অ্যাপ্লিকেশনগুলির জন্য, প্রায়শই পার্শ্ব-চ্যানেল আক্রমণের হুমকি থাকে যেখানে একজন আক্রমণকারী অ্যাপ্লিকেশন কার্যকর করার সময়, ক্যাশিং, ক্র্যাশ ইত্যাদি থেকে দরকারী তথ্য বের করার চেষ্টা করে। যদি এটি একটি উদ্বেগ হয়, উন্নয়নের সময় সতর্কতার সাথে বিবেচনা করা উচিত সুরক্ষামূলক ব্যবস্থাগুলি যেমন ফাংশন এবং ধ্রুব-সময় লুকআপ ব্যবহার করা, মেমরিকে ডিস্কে সংরক্ষণ করা থেকে প্রতিরোধ করা, এবং এই নিবন্ধের সুযোগের বাইরের কিছু অন্যান্য বিবেচনা।

ডেমো

মধ্যে এই পৃষ্ঠাটি শামির গোপন শেয়ারিং স্কিমের একটি ইন্টারেক্টিভ প্রদর্শন রয়েছে। লাইব্রেরির উপর ভিত্তি করে প্রদর্শনী ssss-js, যা নিজেই জনপ্রিয় প্রোগ্রামের একটি জাভাস্ক্রিপ্ট পোর্ট এখন কি করা উচিত. মনে রাখবেন যে বড় মান গণনা করা হচ্ছে , и কিছুটা সময় লাগতে পারে

উত্স: www.habr.com