doc-src/TutorialI/Protocol/Message_lemmas.ML
changeset 21828 b8166438c772
parent 11250 c8bbf4c4bc2d
child 22862 3dd306cb98d2
equal deleted inserted replaced
21827:0b1d07f79c1e 21828:b8166438c772
   123 Addsimps [keysFor_empty, keysFor_Un, keysFor_UN, 
   123 Addsimps [keysFor_empty, keysFor_Un, keysFor_UN, 
   124           keysFor_insert_Agent, keysFor_insert_Nonce, 
   124           keysFor_insert_Agent, keysFor_insert_Nonce, 
   125 	  keysFor_insert_Number, keysFor_insert_Key, 
   125 	  keysFor_insert_Number, keysFor_insert_Key, 
   126           keysFor_insert_Hash, keysFor_insert_MPair, keysFor_insert_Crypt];
   126           keysFor_insert_Hash, keysFor_insert_MPair, keysFor_insert_Crypt];
   127 AddSEs [keysFor_Un RS equalityD1 RS subsetD RS UnE,
   127 AddSEs [keysFor_Un RS equalityD1 RS subsetD RS UnE,
   128 	keysFor_UN RS equalityD1 RS subsetD RS UN_E];
   128 	keysFor_UN RS equalityD1 RS subsetD RS thm "UN_E"];
   129 
   129 
   130 Goalw [keysFor_def] "keysFor (Key`E) = {}";
   130 Goalw [keysFor_def] "keysFor (Key`E) = {}";
   131 by Auto_tac;
   131 by Auto_tac;
   132 qed "keysFor_image_Key";
   132 qed "keysFor_image_Key";
   133 Addsimps [keysFor_image_Key];
   133 Addsimps [keysFor_image_Key];
   156 
   156 
   157 Goal "H \\<subseteq> parts(H)";
   157 Goal "H \\<subseteq> parts(H)";
   158 by (Blast_tac 1);
   158 by (Blast_tac 1);
   159 qed "parts_increasing";
   159 qed "parts_increasing";
   160 
   160 
   161 val parts_insertI = impOfSubs (subset_insertI RS parts_mono);
   161 val parts_insertI = impOfSubs (thm "subset_insertI" RS parts_mono);
   162 
   162 
   163 Goal "parts{} = {}";
   163 Goal "parts{} = {}";
   164 by Safe_tac;
   164 by Safe_tac;
   165 by (etac parts.induct 1);
   165 by (etac parts.induct 1);
   166 by (ALLGOALS Blast_tac);
   166 by (ALLGOALS Blast_tac);
   180 
   180 
   181 
   181 
   182 (** Unions **)
   182 (** Unions **)
   183 
   183 
   184 Goal "parts(G) Un parts(H) \\<subseteq> parts(G Un H)";
   184 Goal "parts(G) Un parts(H) \\<subseteq> parts(G Un H)";
   185 by (REPEAT (ares_tac [Un_least, parts_mono, Un_upper1, Un_upper2] 1));
   185 by (REPEAT (ares_tac [thm "Un_least", parts_mono, thm "Un_upper1", thm "Un_upper2"] 1));
   186 val parts_Un_subset1 = result();
   186 val parts_Un_subset1 = result();
   187 
   187 
   188 Goal "parts(G Un H) \\<subseteq> parts(G) Un parts(H)";
   188 Goal "parts(G Un H) \\<subseteq> parts(G) Un parts(H)";
   189 by (rtac subsetI 1);
   189 by (rtac subsetI 1);
   190 by (etac parts.induct 1);
   190 by (etac parts.induct 1);
   194 Goal "parts(G Un H) = parts(G) Un parts(H)";
   194 Goal "parts(G Un H) = parts(G) Un parts(H)";
   195 by (REPEAT (ares_tac [equalityI, parts_Un_subset1, parts_Un_subset2] 1));
   195 by (REPEAT (ares_tac [equalityI, parts_Un_subset1, parts_Un_subset2] 1));
   196 qed "parts_Un";
   196 qed "parts_Un";
   197 
   197 
   198 Goal "parts (insert X H) = parts {X} Un parts H";
   198 Goal "parts (insert X H) = parts {X} Un parts H";
   199 by (stac (read_instantiate [("A","H")] insert_is_Un) 1);
   199 by (stac (read_instantiate [("A","H")] (thm "insert_is_Un")) 1);
   200 by (simp_tac (HOL_ss addsimps [parts_Un]) 1);
   200 by (simp_tac (HOL_ss addsimps [parts_Un]) 1);
   201 qed "parts_insert";
   201 qed "parts_insert";
   202 
   202 
   203 (*TWO inserts to avoid looping.  This rewrite is better than nothing.
   203 (*TWO inserts to avoid looping.  This rewrite is better than nothing.
   204   Not suitable for Addsimps: its behaviour can be strange.*)
   204   Not suitable for Addsimps: its behaviour can be strange.*)
   205 Goal "parts (insert X (insert Y H)) = parts {X} Un parts {Y} Un parts H";
   205 Goal "parts (insert X (insert Y H)) = parts {X} Un parts {Y} Un parts H";
   206 by (simp_tac (simpset() addsimps [Un_assoc]) 1);
   206 by (simp_tac (simpset() addsimps [thm "Un_assoc"]) 1);
   207 by (simp_tac (simpset() addsimps [parts_insert RS sym]) 1);
   207 by (simp_tac (simpset() addsimps [parts_insert RS sym]) 1);
   208 qed "parts_insert2";
   208 qed "parts_insert2";
   209 
   209 
   210 Goal "(\\<Union>x\\<in>A. parts(H x)) \\<subseteq> parts(\\<Union>x\\<in>A. H x)";
   210 Goal "(\\<Union>x\\<in>A. parts(H x)) \\<subseteq> parts(\\<Union>x\\<in>A. H x)";
   211 by (REPEAT (ares_tac [UN_least, parts_mono, UN_upper] 1));
   211 by (REPEAT (ares_tac [thm "UN_least", parts_mono, thm "UN_upper"] 1));
   212 val parts_UN_subset1 = result();
   212 val parts_UN_subset1 = result();
   213 
   213 
   214 Goal "parts(\\<Union>x\\<in>A. H x) \\<subseteq> (\\<Union>x\\<in>A. parts(H x))";
   214 Goal "parts(\\<Union>x\\<in>A. H x) \\<subseteq> (\\<Union>x\\<in>A. parts(H x))";
   215 by (rtac subsetI 1);
   215 by (rtac subsetI 1);
   216 by (etac parts.induct 1);
   216 by (etac parts.induct 1);
   223 
   223 
   224 (*Added to simplify arguments to parts, analz and synth.
   224 (*Added to simplify arguments to parts, analz and synth.
   225   NOTE: the UN versions are no longer used!*)
   225   NOTE: the UN versions are no longer used!*)
   226 Addsimps [parts_Un, parts_UN];
   226 Addsimps [parts_Un, parts_UN];
   227 AddSEs [parts_Un RS equalityD1 RS subsetD RS UnE,
   227 AddSEs [parts_Un RS equalityD1 RS subsetD RS UnE,
   228 	parts_UN RS equalityD1 RS subsetD RS UN_E];
   228 	parts_UN RS equalityD1 RS subsetD RS thm "UN_E"];
   229 
   229 
   230 Goal "insert X (parts H) \\<subseteq> parts(insert X H)";
   230 Goal "insert X (parts H) \\<subseteq> parts(insert X H)";
   231 by (blast_tac (claset() addIs [impOfSubs parts_mono]) 1);
   231 by (blast_tac (claset() addIs [impOfSubs parts_mono]) 1);
   232 qed "parts_insert_subset";
   232 qed "parts_insert_subset";
   233 
   233 
   376 by (etac analz.induct 1);
   376 by (etac analz.induct 1);
   377 by Auto_tac;
   377 by Auto_tac;
   378 qed "analz_parts";
   378 qed "analz_parts";
   379 Addsimps [analz_parts];
   379 Addsimps [analz_parts];
   380 
   380 
   381 bind_thm ("analz_insertI", impOfSubs (subset_insertI RS analz_mono));
   381 bind_thm ("analz_insertI", impOfSubs (thm "subset_insertI" RS analz_mono));
   382 
   382 
   383 (** General equational properties **)
   383 (** General equational properties **)
   384 
   384 
   385 Goal "analz{} = {}";
   385 Goal "analz{} = {}";
   386 by Safe_tac;
   386 by Safe_tac;
   390 Addsimps [analz_empty];
   390 Addsimps [analz_empty];
   391 
   391 
   392 (*Converse fails: we can analz more from the union than from the 
   392 (*Converse fails: we can analz more from the union than from the 
   393   separate parts, as a key in one might decrypt a message in the other*)
   393   separate parts, as a key in one might decrypt a message in the other*)
   394 Goal "analz(G) Un analz(H) \\<subseteq> analz(G Un H)";
   394 Goal "analz(G) Un analz(H) \\<subseteq> analz(G Un H)";
   395 by (REPEAT (ares_tac [Un_least, analz_mono, Un_upper1, Un_upper2] 1));
   395 by (REPEAT (ares_tac [thm "Un_least", analz_mono, thm "Un_upper1", thm "Un_upper2"] 1));
   396 qed "analz_Un";
   396 qed "analz_Un";
   397 
   397 
   398 Goal "insert X (analz H) \\<subseteq> analz(insert X H)";
   398 Goal "insert X (analz H) \\<subseteq> analz(insert X H)";
   399 by (blast_tac (claset() addIs [impOfSubs analz_mono]) 1);
   399 by (blast_tac (claset() addIs [impOfSubs analz_mono]) 1);
   400 qed "analz_insert";
   400 qed "analz_insert";
   555           ORELSE' etac equalityE));
   555           ORELSE' etac equalityE));
   556 qed "analz_cong";
   556 qed "analz_cong";
   557 
   557 
   558 
   558 
   559 Goal "analz H = analz H' ==> analz(insert X H) = analz(insert X H')";
   559 Goal "analz H = analz H' ==> analz(insert X H) = analz(insert X H')";
   560 by (asm_simp_tac (simpset() addsimps [insert_def] delsimps [singleton_conv]
   560 by (asm_simp_tac (simpset() addsimps [thm "insert_def"] delsimps [thm "singleton_conv"]
   561                             setloop (rtac analz_cong)) 1);
   561                             setloop (rtac analz_cong)) 1);
   562 qed "analz_insert_cong";
   562 qed "analz_insert_cong";
   563 
   563 
   564 (*If there are no pairs or encryptions then analz does nothing*)
   564 (*If there are no pairs or encryptions then analz does nothing*)
   565 Goal "[| \\<forall>X Y. {|X,Y|} \\<notin> H;  \\<forall>X K. Crypt K X \\<notin> H |] ==> analz H = H";
   565 Goal "[| \\<forall>X Y. {|X,Y|} \\<notin> H;  \\<forall>X K. Crypt K X \\<notin> H |] ==> analz H = H";
   589 (** Unions **)
   589 (** Unions **)
   590 
   590 
   591 (*Converse fails: we can synth more from the union than from the 
   591 (*Converse fails: we can synth more from the union than from the 
   592   separate parts, building a compound message using elements of each.*)
   592   separate parts, building a compound message using elements of each.*)
   593 Goal "synth(G) Un synth(H) \\<subseteq> synth(G Un H)";
   593 Goal "synth(G) Un synth(H) \\<subseteq> synth(G Un H)";
   594 by (REPEAT (ares_tac [Un_least, synth_mono, Un_upper1, Un_upper2] 1));
   594 by (REPEAT (ares_tac [thm "Un_least", synth_mono, thm "Un_upper1", thm "Un_upper2"] 1));
   595 qed "synth_Un";
   595 qed "synth_Un";
   596 
   596 
   597 Goal "insert X (synth H) \\<subseteq> synth(insert X H)";
   597 Goal "insert X (synth H) \\<subseteq> synth(insert X H)";
   598 by (blast_tac (claset() addIs [impOfSubs synth_mono]) 1);
   598 by (blast_tac (claset() addIs [impOfSubs synth_mono]) 1);
   599 qed "synth_insert";
   599 qed "synth_insert";